给定一个任意字符串s，我想要一种方法从一大组字符串 M （其中 |M| > 100 万）中快速检索所有字符串 S ⊆ M ，其中 S 的所有字符串具有最小编辑距离 < t （一些最小值阈值）来自s。
在最坏的情况下，如果 M 中没有符合此条件的字符串，则 S 可能为空，而在最好的情况下，S = { s }（完全匹配）。对于介于两者之间的任何情况，我完全预计 S 可能会很大。
一般来说，我希望最大编辑距离阈值是固定的（例如，2），并且需要在任意字符串s上多次执行此操作，因此需要一种有效的方法，因为天真地迭代和测试所有字符串将是太贵了。
虽然我使用编辑距离作为示例指标，但我也想使用其他指标，例如 Jaccard 索引。
任何人都可以对可以实现此目标的现有 Java 实现提出建议，或者指出我解决此问题的正确算法和数据结构吗？
更新#1
从那以后，我了解到度量树正是我所追求的那种结构，它利用距离度量来组织 M 中的字符串子集，基于它们与度量之间的距离。Vantage-Point、BK和其他类似的度量树数据结构和算法似乎都非常适合这类问题。现在，要在 Java 中找到易于使用的实现......
更新#2
使用这个bk-tree和这个Levenshtein 距离实现的组合，我能够成功地从一百万个字符串的集合 (M) 中检索任意字符串的子集，检索时间约为 10 毫秒。