tem*_*def 16 string internationalization trie data-structures
trie数据结构通常是用英语存储字符串的好方法.它通过构建一个树来工作,其中每个边都用字母标记,并且树中标记节点的路径拼出数据结构中的一个字.
这种数据结构在英语中运行良好,因为英语字母中只有"26"字母("合理的"分支因子),这些字符具有连续的ASCII值(因此子指针可以存储在由索引键入的数组中)每个孩子使用的字母),并且有许多带有共同前缀的英语单词(因此结构中有很多冗余).
我是一名母语为英语的人,对其他语言和字母表知之甚少,但似乎很多这些属性并不适用于其他语言.我知道法语,西班牙语,德语和匈牙利语经常使用重音字符,这些字符不会与Unicode空间中的其余字母连续存储.希伯来语和阿拉伯语都有元音标记,通常在每个字母的上方或下方标明.中文使用语标系统,韩语韩文字符由组合在一起的较小字符的三元组组成.
尝试仍然适用于存储在这些语言和字母表中的数据吗？对这类数据使用尝试需要进行哪些更改(如果有)？是否有任何数据结构适用于那些语言和字母表中的字符串,这些字符串特别适合他们但在英语中不会有用或有效？
Jim*_*hel 11
我发现尝试适用于西欧语言,以及西里尔语和许多其他字母语言.想想看,我遇到的唯一语言是中文,日文和其他文字书写系统.对于那些人来说,这个特里是没用的.
英文字符的连续Unicode值实际上并不是一个巨大的好处.虽然它建议简单的节点实现:
CharNode
char
array[26] of CharNode
这种结构并不是特别有用.它可以使事情变得更快,但内存成本相当高.即使在trie的第二级,该阵列也非常稀疏.当你到达第四或第五级时,它几乎都是死空间.我曾经对此做过分析.我会环顾四周,看看我是否还有这些数字.
我发现在节点中有一个可变长度的数组几乎同样快,其中的项目按频率排序.在trie的第二级或第三级之外,我正在寻找的角色几乎总是处于该阵列的第一或第二位置.节省的空间非常大.而不是每个节点26个引用(在我的实现中为104个字节),我有一个单字节计数,然后每个引用五个字节.因此,只要特定节点(大部分时间)的子节点少于21个,我就节省了空间.运行时间损失很小,但在我的应用程序中还不够.
这是我必须对我的trie结构进行的唯一修改,使其支持我正在使用的所有字母语言.正如我所说,我主要使用的是西欧语言,对于那些工作得非常漂亮的人.我知道它确实适用于希伯来语和阿拉伯语,但我不知道它有多好用.它符合我们的目的,但它是否会满足母语使用者是未知的.
我构建的trie对于我们的目的来说效果很好,任何语言的字符都符合Unicode Basic Multilingual Plane.使用代理对时有点奇怪,但我们几乎忽略了这些.基本上,我们只是将代理对视为两个字符并让它继续下去.
您必须决定是否要将重音字符视为单独的字符,或者是否要映射它们.例如,考虑法语单词"garçon",有些人会拼写"garcon",或者因为他们不知道更好或者他们不知道如何制作角色'ç'.根据您使用trie的内容,您可能会发现将重音字符转换为未加重音的等效字符非常有用.但我认为这更像是一个输入清理问题,而不是一个问题.
这是我相当啰嗦的说法,标准特里应该适用于任何字母语言,没有任何语言特定的修改.我没有看到任何明显的方法来使用trie作为语标语言.我对韩语韩语一无所知,所以我不能说trie在那里是否有用.
作为@JimMischel答案的附录,我想提出一个问题,即在其他语言中,通常有多种等效方法来编写同样的东西.越南语(基于拉丁语/英语脚本)是一个特别好的例子,其中带有两个重音的字母很常见.例如,Ặ(U + 1EB6)在技术上也可以用序列Ă+ dot,Ạ+ breve,A + breve + dot,A + dot + breve编写.
Unicode规范化可以通过将字符串转换为标准化规范顺序来解决此问题.有4种不同的变体,NFC,NFKC,NFD和NFKD.我不会在这里详细介绍,但前两个是"组合形式",往往会缩短字符串,将基本字符与其重音分组,而后两个是"分解形式",相反.
韩文是一个有趣的案例:它是一个字母表,尽管一个音节的所有字母都是一起写成的.单个字母和音节块都存在于Unicode中.归一化可以解决这个问题,尽管不同音节的数量非常大.使用NFC/NFKC可能对trie没有用,但在这种情况下,使用NFD/NFKD将音节分解为组成字母会起作用.
其他一些不相关的要点:
| 归档时间： |
|
| 查看次数： |
700 次 |
| 最近记录： |