java - 将字典中的子字符串匹配到其他字符串 : suggestions?

Question

你好 Stack Overflow 的人。我想就以下问题提出一些建议。我正在使用 Java。

我有一个包含多个字符串的数组#1。例如，其中两个字符串可能是:“一个苹果落在牛顿的头上”和“苹果长在树上”。

另一方面，我有另一个数组 #2，其中包含类似 (Fruits => Apple, Orange, Peach; Items => Pen, Book; ...) 之类的术语。我将这个数组称为我的“字典”。

通过将一个数组中的项目与另一个数组进行比较，我需要查看#1 中的项目属于#2 中的哪个“类别”。例如。 #1 中的两者都属于“水果”。

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

我考虑过使用 contains() 方法的哈希集，但它不允许子字符串。我还尝试运行正则表达式，如 (apple|orange|peach|...etc) 并打开不区分大小写的标志，但我读到当术语数量增加时它不会很快(预计最少 200)。最后，我进行了搜索，并正在考虑将 ArrayList 与 indexOf() 一起使用，但我不知道它的性能。我还需要知道哪些术语实际匹配，因此在这种情况下，它将是“Apple”。

请就此问题提出您的看法、想法和建议。

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

感谢您，Stack Overflow 的人们，抽出宝贵的时间! :)

Answer 1

如果您使用来自 Google Collections 的多重 map ，它们具有反转 map 的功能(因此您可以从 {"Fruits"=> [Apple]} 之类的 map 开始，并使用 {"Apple"= > ["Fruits"]}。因此，您可以在一次调用 map 中查找该词并为其找到类别列表。

我希望自己拆分字符串并一次一个地在映射中查找单词，这样我就可以进行词干提取(针对不同的单词结尾进行调整)和停用词过滤。使用 map 应该会获得良好的查找时间，而且它很容易试用。