使用 python - charToIndex 的 Trie 实现

Question

我正在尝试参考 link 中的 Trie 实现 python 代码 https://www.geeksforgeeks.org/trie-insert-and-search/

我想问一个关于以下私有方法的问题：

def _charToIndex(self,ch): 
        # private helper function 
        # Converts key current character into index 
        # use only 'a' through 'z' and lower case 

        return ord(ch)-ord('a')

这如何帮助获取字符的索引，即通过将字符 ch 转换为 Unicode，从中减去 - 'a'

的 Unicode 值

请帮忙说明一下。谢谢！

Answer 1

ord() 给出 Unicode 代码点（整数）。 a-z 的代码点是连续的，因此 ord(ch) - ord('a') 给出字符的索引作为 a 的偏移量。 ord('a') == 97，例如 ord('b') - ord('a') == 1 和 ord('z') - ord('a') == 25。

Answer 2

我喜欢之前的答案，但这就是它的工作原理，而不是你这样做的原因。我认为其目的是使用具有 26 个槽的列表数据结构来包含每个节点的子节点。函数 charToIndex 将 alpha 转换为 int 从 0 到 25（希望如此），您可以在添加或搜索函数期间检查该子节点是否存在。它确实胜过使用列表并且可能必须遍历整个列表才能找到您想要的列表。它也可能会或可能不会击败子节点的哈希图查找，但我认为时间差异很小。该列表可能会加快添加和搜索功能，但不会加快遍历...您仍然必须在遍历期间测试所有 26 个子节点！

使用 python - charToIndex 的 Trie 实现

Trie implementation using python - charToIndex

python-3.x

unicode

trie