So erstellen Sie eine einfache Präfix-index in Java?

Ich habe große Gruppe von urls und ich umsetzen möchten-Vervollständigung. Ich weiß nicht, wie die Komplexität der naive Ansatz, da Sie linear mit der set-Größe:

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

Jetzt weiß ich, dass in einem Hash-Set, die Funktion "contains()" funktioniert in "O(1) -" es gibt aber keine "containsPrefix()". Gibt es eine einfache Möglichkeit, ohne Verwendung einer großen Bibliothek wie Lucene oder Codierung selbst? Ich hätte kein problem es zu tun, aber es scheint übertrieben für so ein einfaches problem, also ich möchte wissen, ob es eine bereits vorhandene Lösung einfach 🙂

Aus meinem informatik-Unterricht erinnere ich mich an einen Baum, der aus der string-Fragmente aber ich habe vergessen, wie es hieß. Es funktionierte folgendermaßen:

[car, care, carrot,carrotville]->

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

P. S.: Wie kann ich die Methoden aufrufen, die gibt alle Zeichenfolgen, die ein string-Präfix? Wie wenn a ist Präfix von b, was b zu a?

  • was möchten Sie tun ? automatisches hinzufügen von text am Anfang jeder Kette ?
  • Ich möchte wissen, welche Zeichenfolgen mein string ist ein Präfix, so kann ich Ihnen die Autovervollständigung-Vorschläge.
InformationsquelleAutor Konrad Höffner | 2012-03-27
  1. 2

    Wenn Sie brauchen, um effizient zu finden Präfixe der strings, verwenden Sie eine Trie, eine Daten-Struktur entwickelt, die genau für diesen Zweck:

    Einem trie oder Präfix-Baum ist ein geordneter Baum-Datenstruktur, die zum speichern verwendet ein assoziatives array, wobei die Schlüssel sind in der Regel Zeichenketten. Im Gegensatz zu einem binären Suchbaum, keine Knoten in der Baum speichert die Schlüssel-verbunden mit dem Knoten; stattdessen, seine position in der Struktur definiert den Schlüssel, mit dem es verbunden ist. Alle Nachfahren eines Knotens haben eine gemeinsame Präfix der Zeichenfolge zugeordnet, die Knoten und die Wurzel verbunden ist mit dem leeren string

    Zwei links mit Beispiel Implementierungen.

    InformationsquelleAutor Óscar López
  2. 1

    Langer Zeit habe ich einen einfachen Trie-Implementierung hier:

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

    Dies ist jedoch nicht ein kompakter Trie, erzeugt so ein Knoten pro Zeichen, wodurch eine kompakte eins ist ein bisschen schwieriger.

    • Das ist großartig! Ich habe nichts dagegen, wenn es einen Knoten pro Charakter, aber ich lasse die Frage offen, nur für den Fall jemand hat man mit Kombiwetten.
    • Np, kompakte version verwendet, etwa %50 weniger Knoten (zumindest für türkische Wörter in einem Wörterbuch) Dies ist D er test-code, so können Sie in Aktion sehen, ich hoffe es sind keine bugs 🙂 code.google.com/p/triebag/source/browse/trunk/test/triebag/...
    • Ich habe versucht, aus Ihrem SimpleTrie aber es scheint nicht zu funktionieren für mich. Zuerst der Konstruktor wurde nicht öffentlich und nach habe ich geändert, den folgenden test zurückgegeben nichts: SimpleTrie<String> trie = new SimpleTrie<>(); trie.add("x","x"); trie.add("xy","xy"); Iterator it = trie.getItemsWithPrefix("x"); while(it.hasNext()) System.out.println(it.next());
    InformationsquelleAutor mdakin
  4. 0

    Die Regexp-Implementierung java.util.regex.Muster können effizient zu handhaben Präfixe:

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

    Können Sie testen alle Präfixe:

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

    Hinweis: für die Einfachheit, Präfix-strings sind nicht entgangen. Regexp-Zeichen [, ], \, *, ?, $, ^, (, ), {, } und | werden mit dem Präfix \.

    InformationsquelleAutor Tires
Schreibe einen Kommentar