Textsuche in Liste



  • Hallo,

    möchte in einer Liste von Texten nach einem Suchtext suchen.

    Liste:
    [0] "Apfel"
    [1] "Banane"
    [2] "Kirsche"

    Suchtext: "a"
    Ergebnis: Eintrag 0, Zeichen 0; Eintrag 1 Zeichen 1 und Zeichen 3

    Suchtext: "pfel"
    Ergebnis: Eintrag 0, Stelle 1

    Jedes Mal alle Listeneinträge nach dem Substring zu durchsuchen kommt nicht in Frage, da zu langsam. Alles in eine DB rein und dann SQL Abfrage ist auch nicht machbar.

    Das einzige, was mir bisher als möglicherweise brauchbar erscheint, ist ein Suffix Tree: https://en.wikipedia.org/wiki/Suffix_tree
    Hat jemand damit Erfahrungen? Andere Vorschläge? Wichtig ist vor allem, dass die Suche schnell ist. Wenn anfangs ein Suchbaum aufgebaut werden muss (was wiederum Zeit braucht), so wäre das ok.



  • Liste sortiert oder unsortiert?



  • Ob die Liste sortiert oder unsortiert ist, ist doch völlig egal.

    Soweit ich das sehe wird nur die Möglichkeit bleiben jeden Eintrag zu durchsuchen. Von wie vielen Einträgen reden wir denn, dass dies zu lang dauert?



  • Ohne weitere Einschränkung kann das nicht effizient gelöst werden (im Worst-Case ist jeder Eintrag ein Treffer und dann können wir auch gleich alles durchgehen).
    - Wie lang sind die Texte?
    - Wie viele Einträge haben wir?
    - Was soll gemacht werden, wenn es zu viele Matches gibt?



  • jusles schrieb:

    Ohne weitere Einschränkung kann das nicht effizient gelöst werden (im Worst-Case ist jeder Eintrag ein Treffer und dann können wir auch gleich alles durchgehen).
    - Wie lang sind die Texte?
    - Wie viele Einträge haben wir?
    - Was soll gemacht werden, wenn es zu viele Matches gibt?

    1. kurz, im Schnitt vielleicht um die 15 Buchstaben
    2. viele
    3. es genügt, die ersten paar Treffer zu liefern

    Was spricht gegen den Suffix Tree?



  • suchenundfinden schrieb:

    jusles schrieb:

    Ohne weitere Einschränkung kann das nicht effizient gelöst werden (im Worst-Case ist jeder Eintrag ein Treffer und dann können wir auch gleich alles durchgehen).
    - Wie lang sind die Texte?
    - Wie viele Einträge haben wir?
    - Was soll gemacht werden, wenn es zu viele Matches gibt?

    1. kurz, im Schnitt vielleicht um die 15 Buchstaben
    2. viele
    3. es genügt, die ersten paar Treffer zu liefern

    Was spricht gegen den Suffix Tree?

    Probier den Suffix-Tree mal aus. Er ist schnell, braucht aber sehr viel Speicher.

    Mein Vorschlag wäre, die Hashs von allen Substrings auszurechnen (sind nur etwa 15*14/2 pro Eintrag) und pro Hash die ersten paar Treffer zu speichern. Das ist extrem schnell und dürfte etwas platzsparender sein.



  • inflames2k schrieb:

    Ob die Liste sortiert oder unsortiert ist, ist doch völlig egal.

    wenn man keine ahnung hat, usw. 🙄

    Schliesslich kann man wenn die liste sortiert ist binär suchen was wesentlich schneller ist.

    inflames2k schrieb:

    Soweit ich das sehe wird nur die Möglichkeit bleiben jeden Eintrag zu durchsuchen

    sihst du falsch. Jeden eintrag durchsuchen wäre O(n). Binär suche ist O(log(n)).



  • sort? schrieb:

    inflames2k schrieb:

    Ob die Liste sortiert oder unsortiert ist, ist doch völlig egal.

    wenn man keine ahnung hat, usw. 🙄

    Full ack.

    Lies mal den OP durch und erkläre, wie man nach einem Subtext binarysearcht.

    Man kann natürlich alle Suffixe sortieren und nach ihnen binarysearchen.



  • jusles schrieb:

    suchenundfinden schrieb:

    jusles schrieb:

    Ohne weitere Einschränkung kann das nicht effizient gelöst werden (im Worst-Case ist jeder Eintrag ein Treffer und dann können wir auch gleich alles durchgehen).
    - Wie lang sind die Texte?
    - Wie viele Einträge haben wir?
    - Was soll gemacht werden, wenn es zu viele Matches gibt?

    1. kurz, im Schnitt vielleicht um die 15 Buchstaben
    2. viele
    3. es genügt, die ersten paar Treffer zu liefern

    Was spricht gegen den Suffix Tree?

    Probier den Suffix-Tree mal aus. Er ist schnell, braucht aber sehr viel Speicher.

    Mein Vorschlag wäre, die Hashs von allen Substrings auszurechnen (sind nur etwa 15*14/2 pro Eintrag) und pro Hash die ersten paar Treffer zu speichern. Das ist extrem schnell und dürfte etwas platzsparender sein.

    ok, vielen Dank, ich werde das mal probieren.



  • wieviele Listeneinträge hast du denn?


Anmelden zum Antworten