D..*_*D.. 5 string algorithm graph
我试图以简洁的方式存储大量字符串,以便可以非常快速地分析/搜索它们.
有向无环字图(DAWG)非常适合这个目的.但是,我没有首先要包含的字符串列表,因此必须以增量方式构建.另外,当我搜索一个字符串时,我需要带回与结果相关的数据(不仅仅是一个布尔说,如果它存在).
我在这里找到了有关字符串数据跟踪的DAWG修改的信息:http://www.pathcom.com/~vadco/adtdawg.html它看起来非常非常复杂,我不确定我是否有能力编写它.
我还发现了一些描述增量构建算法的研究论文,尽管我发现一般来说研究论文并不是很有帮助.
我认为我不够先进,无法自己将这两种算法结合起来.是否有已经具备这些功能的算法的文档,或者具有良好内存使用和速度的替代算法？
小智 7
我写了ADTDAWG网页.在施工后添加单词不是一种选择.该结构只不过是4个无符号整数类型的数组.它被设计为包含总CPU缓存的不可变,以及最小的多线程访问复杂性.
该结构是一个自动机,形成一个最小和完美的哈希函数.它是为速度而构建的,同时使用显式堆栈递归遍历.
已发布,最多支持18个字符.包括所有26个英国字符将需要进一步增加.
我的建议是使用标准的Trie,每个节点都存储一个数组索引.Ya,它似乎是婴儿,但每个END_OF_WORD节点只代表一个单词.ADTDAWG是传统DAWG中每个END_OF_WORD节点的解决方案,代表许多单词.
最小和完美的哈希表不是那种你可以随时组合在一起的东西.
我正在寻找其他工作或工作,所以请联系我,我会尽我所能.现在,我只能说,在经常更改的结构上使用大量优化是不现实的.