Wie "Autocomplete"-Funktion am Besten implementieren?

[Gast]

Wie kann man am Besten eine Autocomplete-Funktion implementieren? Ich hatte mir Lucene bzw. Solr angesehen aber da funktioniert das mehr schlecht als recht (Stichwort: "TooManyClauses"), weil das offensichtlich nicht wirklich dafür gedacht ist (basiert auf ganzen Wörtern). Was nutzen denn große Seiten für sowas? Ich hatte was von Trie-Suchbäumen gelesen aber brauchen die dann nicht extrem viel RAM? Konkret gehts um etwa 1 Million Überschriften, die damit durchsucht werden sollen.

[samm]

Warum sollten Tries viel RAM brauchen? Ist doch eine effiziente Methode um ein solches Problem zu lösen. Musst halt Speicherverbrauch vs. Suchtiefe balancieren.

[RattuS]

Die Trie-Bäume dürften am effizientesten sein. Sparen kannst du nur noch, wenn du die Verzweigung von Anfang an kleiner hälst, sprich erst ab einem Begriff > 5 Zeichen (z.B.) anfängst zu suchen.