Szybkie porównywanie ciągu znaków z kolekcją w Javie

Question

Próbuję obliczyć odległości edycyjne ciągu od kolekcji, aby znaleźć najbliższe dopasowanie. Mój obecny problem polega na tym, że kolekcja jest bardzo duża (około 25000 pozycji), więc musiałem zawęzić zestaw do samych łańcuchów o podobnej długości, ale to wciąż ograniczyłoby go do kilku tysięcy ciągów, a to wciąż jest bardzo powolne. Czy istnieje baza danych, która pozwala na szybkie wyszukiwanie podobnych ciągów lub czy istnieje inny sposób rozwiązania tego problemu?

Answer 1

Brzmi jak BK-tree może być tym, co chcesz. Oto artykuł omawiający je: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees. A quick Google daje pewne implementacje Java.

Answer 2

Jeśli kryteria "podobne" definiują całkowite uporządkowanie, powinieneś być w stanie zdefiniować komparator i użyć TreeSet, aby znaleźć najbliższe dopasowania (np. Używając metody sufitu i podłogi).

Answer 3

Levenshtein Automaty pozwalają na szybki wybór zestawu słów z dużego słownika, tak aby znajdowały się w podanej odległości Levenshtein od danego słowa.

Patrz: Schulz K, Mihov S. (2002) Fast String Correction with Levenshtein-Automata.