Nie pisałem, że Twój ma O(log n), tylko że MÓJ, który zaproponowałem (opisowo) kilka postów wyżej.
I tam jest trie lub tablica posortowana zbudowana ze słów przetłumaczonych na kody klawiszy, powiązane później z właściwymi słowami.
To jest różnica. Ale swoją drogą w przypadku trie, to chyba w tej swojej analizie przesadziłeś z wykładniczą złożonością. Nawet jak zrobisz trie na literkach, a nie klawiszach, to i tak przeglądanie wszystkich adekwatnych ścieżek nie będzie wykładnicze, bo... większości ścieżek w trie zwyczajnie nie będzie. Więc Twoja analiza jest błędna. Pisałem już, że generowanie WSZYSTKICH przedrostków jest głupie i nie będzie działać.
@Azarien: w przypadku kilkuset tysięcy słów maks. 25 znakowych kwestia czy złożoność jest wykładnicza, czy logarytmiczna, na powolnym procesorze komórki ma bardzo duże znaczenie. I czy wyszukiwanie wyrazu będzie liniowe czy logarytmiczne też.
// Dopisane.
Poniżej kompletna implementacja T9 w 4 linijkach (jeśli nie liczyć nagłówków funkcji).
Jeśli n - liczba słów, to:
Złożoność budowania słownika: O(n log n)
Złożoność wyszukiwania pierwszego pasującego słowa: O(log n)
Złożoność przechodzenia do następnego znalezionego słowa: O(1)
Zajętość pamięciowa słownika: O(n)
Złożoność wyszukiwania nie zależy od długości wyrazów.
import collection.immutable.{SortedMap, TreeMap}
val chars = Map() ++ (('a' to 'z' toList) zip List(2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9))
def translate(s: String): String =
s.toArray map chars mkString
def buildTree(words: List[String]): SortedMap[String, String] =
TreeMap[String, String]() ++ (words map (w => (translate(w) + w) -> w))
def find(tree: SortedMap[String, String], prefix: String): Iterable[String] =
tree from prefix until (prefix + '\u6666') values
Test:
scala> val t = buildTree(List("moja", "mama", "ma", "nowego", "kota"))
t: scala.collection.immutable.SortedMap[String,String] = Map((5682,kota), (62,ma), (6262,mama), (6652,moja), (669346,nowego))
scala> find(t, "6").toList
res34: List[String] = List(ma, mama, moja, nowego)
scala> find(t, "62").toList
res35: List[String] = List(ma, mama)
scala> find(t, "66").toList
res36: List[String] = List(moja, nowego)
scala> find(t, "669").toList
res37: List[String] = List(nowego)
scala> find(t, "665").toList
res38: List[String] = List(moja)
scala> find(t, "6659").toList
res39: List[String] = List()
Modyfikację tak, aby działały priorytety pozostawiam jako pracę domową. :P