Pattern Matching in O(log N)



  • Könnte man einen balancierten binären Baum hernehmen um Pattern Matching, also Suchen nach einem Text in einem anderen Text, in O(log N) zu machen? Ich könnte mir vorstellen in den Blättern Hashcodes von Teilstrings zu speichern und die dann segment-weise zu vergleichen??



  • Was ist Dein N? Die Größe des Patterns bzw. des Textes kann es schonmal nicht sein: Du mußt schließlich jedes Zeichen mindestens einmal anschaun, das ergibt dann aber schon O(N). Oder willst Du die Vorverarbeitungskosten nicht reinrechnen? Also den Text irgendwie vorverarbeiten und danach sollen Teilstring effizient gefunden werden? Dann hängt das aber auch immer noch von der Größe Deines Patterns ab.



  • ich glaube nicht das es möglich ist pattern matching zu machen ohne nicht jeden buchstaben min. einmal zu betrachten. wenn du einige teilstrings als hashwert speicherst könnte es sein das der teilstring, den du suchst gar nicht in deinem baum ist. sehe da keine möglichkeit.
    wenn du jedes element der potenzmenge deines strings in eine hashmap packst, solltest du pattern matching in O(1) machen können, allerdings mit einem platzverbrauch von O(2^n). also naja...



  • das kann man mit Tries.
    http://en.wikipedia.org/wiki/Trie
    der Aufbau des selbigen ist aber aufwendig.


Log in to reply