In meinen Tests hat der Horspool schlechter abgeschnitten als Quicksearch. Vielleicht zeigst du mal deine Version, meine Tests beruhten auf den Implementierungen von
Charras & Lecroq.
Einen sehr interessanten Ansatz habe ich
hier entdeckt. Er basiert auf Sundays Arbeit, kann jedoch die Anzahl der Vergleiche halbieren. Leider ist er in der Praxis bei meinen Tests langsamer, was wohl an dem Overhead der indirekten Indizierung liegt. Ein Paradebeispiel, das theoretische Überlegungen nicht immer das Maß aller Dinge ist.
Noch etwas zu Tries, DAWGs etc. Das sind wahre Performancewunder, aber leider verbraten sie so dermaßen viel Speicher, das sie sich in der Praxis nicht zum Suchen in langen Texten eignen. Als Wörterbuch sind sie dagegen wirklich 'kinky'.
Hab ich erwähnt, das ich den QSearch für eine sehr schnelle Adresssuche verwende? Wir haben ca. 500.000 Kundenadressen, und die Disponenten kenn manchmal nicht den vollständigen Kundennamen, sondern nur Teile, oder Straße etc. Mit Quicksearch kann ich eine 'while-you-type' Suche in Echtzeit durchführen. Der Disponent tippt also 'Kassu' ein, das Teil findet 'Dipl. Ing. Kassupke' ,'Die Kassupke Company' etc.
Die gewünschte (und mit FastCode.org erreichte) teilweise drastische Verbesserung hat nur sportliche Aspekte, weil man den Unterschied in meinem Anwendungsfall eh nicht merkt.