将字典中的子字符串与其他字符串匹配:建议？

Question

Hellow Stack Overflow人.我想对以下问题提出一些建议.我正在使用Java.

我有一个带有多个字符串的数组#1.例如,两个字符串可能是:"苹果落在牛顿的头上"和"苹果在树上生长".

另一方面,我有另一个数组#2,其中的术语如(Fruits => Apple,Orange,Peach; Items => Pen,Book; ...).我把这个数组称为我的"字典".

通过比较从一个阵列到另一个阵列的项目,我需要看到来自#1的项目属于哪个"类别"从#2落入.例如,来自#1的两者都属于"水果".

我最重要的考虑因素是速度.我需要快速完成这些操作.允许恒定时间检索的结构将是好的.

我考虑使用contains()方法的Hashset,但它不允许子字符串.我也尝试运行像(apple | orange | peach | ...等)的正则表达式,并且不区分大小写标记,但我读到当条款数量增加时(预期最小值为200),它将不会很快.最后,我搜索了,并考虑使用带有indexOf()的ArrayList,但我不知道它的性能.我还需要知道哪些术语实际匹配,所以在这种情况下,它将是"Apple".

请提供您对此问题的看法,想法和建议.

我看到了Aho-Corasick算法,但关键词/术语很可能经常改变.所以我认为我不能使用它.哦,我不是文本挖掘和数学方面的专家,所以请详细说明复杂的概念.

感谢Stack Overflow人,您的时间!:)

Answer 1

后缀树或类似的数据结构适合您的应用程序吗？它提供 O(m) 字符串查找，其中 m 是搜索字符串的长度，在 O(n ² ) 之后——或者通过一些技巧更好——初始设置，并且通过一些额外的努力，您可以关联任意数据，例如对某个类别的引用，以及字典中的完整单词。如果您不想自己编码，我相信BioJava库包含一个实现。

您还可以在初始设置后将字符串添加到后缀树，尽管成本仍然约为 O(n ² )。如果您添加简短的单词，这可能不是什么大问题。