Jak utworzyć prosty indeks prefiksu w Javie?

Question

Mam duży zestaw adresów URL i chcę zaimplementować autouzupełnianie. Nie lubię złożoność naiwnego podejścia, jak to jest liniowy z wielkością zestawie:

for(String url: urls) if(url.startsWith(input) {doSomething();} 

Teraz wiem, że w Hash, funkcja „zawiera()” prace w „O (1) "ale nie ma" zawieraPrefix() ". Czy istnieje prosty sposób bez użycia dużej biblioteki, takiej jak Lucene, czy też samodzielnego kodowania? Nie miałbym problemu z tym, ale wydaje się, że jest to zbyt prosty problem, więc chcę wiedzieć, czy istnieje proste rozwiązanie :-)

Z moich zajęć informatycznych pamiętam drzewo, które składa się z fragmentów smyczków, ale Zapominam, jak to się nazywało. To działało tak:

[car, care, carrot,carrotville]-> 

car 
| 
-/ 
-e 
-rrot 
    | 
    ----ville 

P.S .: Jak wywołać metody, które zwracają wszystkie ciągi, których ciąg jest przedrostkiem? Podobnie jak w przypadku przedrostka b, jaki jest b do a?

Answer 1

Jeśli chcesz skutecznie znaleźć prefiksy ciągów, użyj Trie, struktury danych przeznaczone właśnie do tego celu:

A trie lub drzewa prefiks, jest uporządkowana struktura danych drzewo, które służy do przechowuj tablicę asocjacyjną, w której klucze są zwykle ciągami. W przeciwieństwie do binarnego drzewa wyszukiwania żaden węzeł w drzewie nie przechowuje klucza skojarzonego z tym węzłem; zamiast tego jego pozycja w drzewie definiuje klucz, z którym jest skojarzony. Wszystkie potomkami węzła mają wspólny przedrostek łańcucha związanego z tym węźle, a korzeń jest związany z pustym ciągiem

dwa linki z sampleimplementations.

Answer 2

Dawno temu kładę prostą implementację TRIE tutaj:

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

Jednak nie jest to kompaktowy Trie, dlatego tworzy jeden węzeł na znak, tworząc zwarty jeden jest nieco trudniejsze.

Answer 3

Doskonałą alternatywą algo jest ternary search tree (więcej pamięci efektywne) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree

o to trie w java http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 4

RegExp realizacja java.util.regex.Pattern mogą skutecznie obsługiwać przedrostki:

StringBuilder buffer = new StringBuilder(); 
for (String prefix : prefixes) { 
    if (buffer.length() > 0) 
     buffer.append("|"); 
    buffer.append(prefix); 
} 
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")"); 

można przetestować wszystkie przedrostki:

boolean containsPrefix = prefixPattern.matcher(stringToTest).find(); 

Uwaga: dla uproszczenia ciągi prefiksów nie są chronione. Znaki Regexp [,], \, *,?, $, ^, (,), {,} I | musi być poprzedzony przez \.