Patricia Tree 简称PAT tree。 它是 trie 结构的一种特殊形式。是目前信息检索领域应用十分成功的索引方法，它是1992年由Connel根据《PATRICIA——Patrical Algorithm to Retrieve Information Coded in Alphanumeric》算法发展起来的。
PAT tree 在字符串子串匹配 上有这非常优异的表现，这使得它经常成为一种高效的全文检索算法，在自然语言处理领域也有广泛的应用。其算法中最突出的特点就是采用半无限长字串(semi-infinite string 简称 sistring) 作为字符串的查找结构
2021-12-05 12:34:47
244KB
1