Java 中基于度量距离的快速字符串检索
Fast string retrieval based on metric distance in Java
给定一个任意字符串s，我想要一种方法来快速从一大组字符串中检索所有字符串 S ⊆ M M（其中 |M| > 100 万），其中 S 的所有字符串与 s 的最小编辑距离 < t（某个最小阈值）。
在最坏的情况下，如果 M 中没有字符串符合此条件，则 S 可能为空，在最好的情况下，S = {s} （完全匹配）。对于介于两者之间的任何情况，我完全希望 S 可能非常大。
一般来说，我希望最大编辑距离阈值是固定的（例如，2），并且需要对任意字符串执行多次此操作s，因此需要一种有效的方法，因为天真地迭代和测试所有字符串的成本太高。
虽然我使用编辑距离作为示例指标，但我也想使用其他指标，例如 Jaccard 指数。
任何人都可以就可以实现此目的的现有 Java 实现提出建议，或者为我指出解决此问题的正确算法和数据结构吗？
更新#1
从那以后我了解到 Metric trees are precisely the kind of structure I am after, which exploits the distance metric to organise subsets of strings in M based on their distance from each other with the metric. Both Vantage-Point, BK 和其他类似的度量树数据结构和算法似乎是解决此类问题的理想选择。现在，要在 Java...
中找到易于使用的实现
更新#2
结合使用此 bk-tree and this Levenshtein distance 实现，我成功地能够从一百万个字符串的集合 (M) 中检索任意字符串的子集，检索时间约为 10 毫秒。
虽然我自己从未尝试过，但可能值得一看 Levenshtein Automaton。我曾将这篇文章添加为书签，它看起来相当复杂，并提供了几个代码片段：
Damn Cool Algorithms: Levenshtein Automata
正如 HW 已经提到的，您将无法避免检查字典中的每个单词。但是，自动机将加快计算距离的速度。将其与字典的有效数据结构（例如维基百科文章中提到的 Trie）结合起来，您可能能够加速当前的方法。
BK trees就是为这种情况设计的。它适用于公制距离，例如 Levenshtein 或 Jaccard 指数。
给定一个任意字符串s，我想要一种方法来快速从一大组字符串中检索所有字符串 S ⊆ M M（其中 |M| > 100 万），其中 S 的所有字符串与 s 的最小编辑距离 < t（某个最小阈值）。
在最坏的情况下，如果 M 中没有字符串符合此条件，则 S 可能为空，在最好的情况下，S = {s} （完全匹配）。对于介于两者之间的任何情况，我完全希望 S 可能非常大。
一般来说，我希望最大编辑距离阈值是固定的（例如，2），并且需要对任意字符串执行多次此操作s，因此需要一种有效的方法，因为天真地迭代和测试所有字符串的成本太高。
虽然我使用编辑距离作为示例指标，但我也想使用其他指标，例如 Jaccard 指数。
任何人都可以就可以实现此目的的现有 Java 实现提出建议，或者为我指出解决此问题的正确算法和数据结构吗？
更新#1
从那以后我了解到 Metric trees are precisely the kind of structure I am after, which exploits the distance metric to organise subsets of strings in M based on their distance from each other with the metric. Both Vantage-Point, BK 和其他类似的度量树数据结构和算法似乎是解决此类问题的理想选择。现在，要在 Java...
中找到易于使用的实现更新#2
结合使用此 bk-tree and this Levenshtein distance 实现，我成功地能够从一百万个字符串的集合 (M) 中检索任意字符串的子集，检索时间约为 10 毫秒。
虽然我自己从未尝试过，但可能值得一看 Levenshtein Automaton。我曾将这篇文章添加为书签，它看起来相当复杂，并提供了几个代码片段：
Damn Cool Algorithms: Levenshtein Automata
正如 HW 已经提到的，您将无法避免检查字典中的每个单词。但是，自动机将加快计算距离的速度。将其与字典的有效数据结构（例如维基百科文章中提到的 Trie）结合起来，您可能能够加速当前的方法。
BK trees就是为这种情况设计的。它适用于公制距离，例如 Levenshtein 或 Jaccard 指数。