Jakiej struktury danych użyć – slownik T9

Potrzebuje pomocy z ponizszym zadaniem:
Uzywajac jezyka JAVA mam napisac program (cos w rodzaju slownika T9 jak w telefonach komorkowych).

Program ma miec podstawowy interfejs graficzny z 12 klawiszowa klawiatura (taka jak w komorkach) i pole tekstowe gdzie wpisujemy tekst.

Na poczatek tworzymy slownik wyrazow na podstawie jakiegos tekstu (tekst potem wczutujemy do programu). Kazdy wyraz zostanie zapisany w tablicy (array) a obok niego podana jest jego czestotliwosc wystepowania.

Po wpisaniu pierwszej litery z klawiatury, program powinien wyswietlic najczesciej uzywane slowa zaczynajace sie z tej litery tak, zeby mozna bylo szybko wybrac ktorys z sugerowanych wyrazow.
Po wpisaniu kazdej kolejnej litery program powinien zawezic liczbe wyrazow i znowu wyswietlic liste z najczesciej uzywanymi slowami.
Jesli po wpisaniu jakiejs kombinacji klawiszy, nie ma zadnych sugestii, powinna pojawic sie opcja aby recznie dodac slowo do slownika.

Moj najwiekszy problem w tej chwili, to: Jakiej struktury danych uzyc, do stworzenia takiego programu i jak napisac algorytm? Chcialem jeszcze zaznaczyc ze zalezy mi na jak najlepszej wydajnosci = najmniejszej zlozonosci algorytmu. Kilka sugestii ponizej:

1) Dwu wymiarowe tablice (2 dimensional arrays).
Ta opcja byla by chyba bardzo nieefektywna, ze wzledu na marnowanie miejsca. Jesli np: najdluzszy wyraz mialby dlugosc ‘n’, trzeba byloby stworzyc miejsce dla 26^n (26 do potegi n) * 26 bo tyle jest liter w angielskim alfabecie?!?
Nie wiem czy to co napisalem powyzej ma sens, tak wiec prosze podajcie wszystkie ZA i PRZECIW tej struktury danych do implementacji powyzszego programu (czy to w ogole mozliwe).

2) Tablica Mieszajaca (Hash Table).
Slyszalem, ze tablica mieszajaca jest dobra do znajdowania konkretnych elementow (wyrazow), ale w tym przypadku, po wcisnieciu kazdej litery, powinnismy otrzymac liste sugestii, tak wiec... czy Tablica Mieszajaca w tym przypadku bylaby dobrym rozwiazaniem? Jesli tak, jak to by wygladalo?

3) Odmiana Drzewa Binarnego (z angielskiego: TRIE)
Mniej znana struktura danych, ktora z tego co sie dowiedzialem wydaje sie byc najlepsza do implementacji powyzszego programu. Niestety nie moglem znalezc za wiele informacji w internecie na temat TRIE’s i nie wiem dokladnie jak by to mialo dzialac... Bylbym wdzieczny, gdyby ktos wypowiedzial sie rowniez na temat tej struktury danych do implementacji powyzszego programu. Czy jest ona najlepsza, czy moze jedyna?
 
Ponizej moje ‘wyobrazenie’ implementacji programu z uzyciem TRIE’s (odmiana Drzewa Binarnego) oraz pare pytan. Uprzedzam, ze to co napisalem moze sie nie trzymac kupy i nie miec sensu... ale chcialbym przedstawic jak to obecnie wyglada w mojej glowie, zebyscie mogli mi w jakis sposob pomoc. Bylbym bardzo wdzieczny za poprawnienie ponizszego tekstu, lub opisanie poprawnego dzialania programu z uzyciem drzewa TRIE wlasnymi slowami.

a) Samo drzewo TRIE implementujemy uzywajac ArrayList dostepnej w JAVA?
b) Wartosc kazdego Noda w tym drzewie to link do obiektu (ArrayList, w ktorym znowu przechowujemy 26 obiektow z literami od A do Z i z ich liczbowa czestotliwoscia wystepowania).
c) I tak, jesli w programie wpiszemy jako szukane slowo pierwsza litere ‘C’, to program odwiedzi pierwszy Nod w drzewie (header), i stamtad przejdzie to obiektu w tablicy o 2 indeksie (litery ‘C’).
d) Teraz idziemy o jeden poziom w dol
e) Odczytujemy liste wszystkich slow zaczynajacych sie na ‘C’. (TYLKO NIE WIEM JAK ODCZYTUJEMY TE SLOWA??)
f) Sprawdzamy, ktore ze slow sa najczesciej uzywane (przez porownanie czestotliwosci poszczegolnych slow)
g) Zwracamy kilka najczesciej uzywanych slow zaczynajacych sie na ‘C’. (I TUTAJ NIE WIEM W JAKI SPOSOB MOZEMY POLACZYC NASZE AKTUALNE MIEJSCE W DRZEWIE 'NP: 'C' z tablica calego slownika, z ktorego bedziemy wczytywac wszystkie slowa zaczynajace sie na 'C').
h) Po dodaniu kolejnej litery ‘C’ + ‘A’, program odwiedza 1 Nod i przechodzi do indeksu 2 (z litera ‘C’)
i) Nastepnie idzie o jeden poziom nizej (na lewo od C, bo A < C), odwiedza Nod i wchodzi do tablicy (array), gdzie wchodzi na 0 index (gdzie jest litera ‘A’).
j) Nastepnie program odczytuje liste wszystkich slow zaczynajacych sie na ‘CA’. CZY COS TAKIEGO MOZNA ZROBIC POPRZEZ POROWNANIE LITER NA PIERWSZYCH DWOJ MIEJSCACH WYRAZU (charAt(0) i charAt(1))??
k) Program sprawdza, ktore slowa sa najczesciej uzywane, poprzez porownanie wartosci ‘czestotliwosc’ pomiedzy poszczegolnymi slowami.</span>

Zastanawiam sie do czego (w jaki sposob) mozna uzyc indeksowania samego drzewa zeby miec szybki dostep do konkretnego noda? Np: Skad bedziemy wiedziec, ze slowa rozpoczynajace sie na ‘CA’ beda ponizej Noda o indeksie np: 20, a nie w Nodzie o indeksie 100?

Do tej pory skupialem sie na rozwiazaniu problemu przyjmujac, ze uzywamy klawiatury QWERTY, gdzie kazdy klawisz odpowiada 1 literze.
Kolejnym krokiem i zarazem nastepnym problemem bedzie implementacja programu z uzyciem 12 klawiszowej klawiatury telefonu, gdzie 1 klawisz odpowiada 3 lub 4 literom... co na pewno uczyni caly algorytm bardziej zlozonym...

Pozdrawiam i z gory dziekuje za wszelka pomoc/wskazowki

Trie wydaje się tutaj najlepszym wyjściem, jeśli chcesz mieć to "podpowiadanie" słów. Jeśli walniesz pełne drzewko, tzn na każdym poziomie masz przypięty cały alfabet do każdej literki to obliczenie gdzie znajduje się jakieś słowo (o ile istnieje) jest trywialne.
Ale twoje rozwiązanie jest trochę zabójcze pamięciowo, bo takie drzewko dla słów 8 literowych to będzie
208827064576 bajtów, jeśli jedna literka = jeden char, czyli ~194 GB. Masz tyle ramu?
Tak też myślałem ;)

Drzewka implementuje się na listach. Poza tym powinieneś dodawać daną literkę dopiero kiedy jest potrzebna (kiedy dodajesz słowo do słownika) no i musisz mieć dodatkowo znakcznik końca slowa, zeby było wiadomo jakie słowo jest w słowniku, a jakiego tam nie ma. Tzn dla drzewka

      A 
    R   S
  A       *
*

jedyne słowa w slowniku to ARA i AS, a słowo np. AR w słowniku nie jest.

Shalom napisał(a)

Trie wydaje się tutaj najlepszym wyjściem, jeśli chcesz mieć to "podpowiadanie" słów.

To podpowiadanie spokojnie można zrealizować na secie lub innym posortowanym zbiorze danych. Myślę sobie, że użycie drzewa trie niepotrzebnie skomplikuje rozwiązanie zadania, a zysk będzie żaden.

0x666 napisał(a)

Shalom napisał(a)

Trie wydaje się tutaj najlepszym wyjściem, jeśli chcesz mieć to "podpowiadanie" słów.

To podpowiadanie spokojnie można zrealizować na secie lub innym posortowanym zbiorze danych. Myślę sobie, że użycie drzewa trie niepotrzebnie skomplikuje rozwiązanie zadania, a zysk będzie żaden.

A jak chcesz dopasowac czesc wpisanego wyrazu do elementow seta? Niby posortowany, ale i tak musisz strzelac mniej wiecej gdzie sie znajdzie litera. TRIE moim zdaniem lepsze.

Zysk będzie pamięciowy ;) Kolosalny tak nawiasem mówiąc. Ale faktycznie, jeśli zalezy komuś na prostocie implementacji to użycie posortowanej zbioru danych. Tylko ze pozostają inne kwestie. Jeśli użyje się LinkedList to rozbudowa słownika będzie prosta, ale szukanie słowa w czasie O(n). Jeśli użyje sie jakiegos ArrayList to dodawanie moze być wolniejsze (kwestia jak często będzie sie powiększala tablica) ale szukanie w O(logn).
Jeśli to ma być Java to chyba najłatwiej będzie przetestować która kolekcja najbardziej nam pasuje, albo przemyśleć jakie operacje będą wykonywane często a jakie rzadko (jeśli słowa będą dodawane bardzo rzadko, a często wyszukiwane, a tak chyba będzie, to ArrayList spokojnie wystarczy).
Użycie seta wyeliminuje powtórzenia.

A jak chcesz dopasowac czesc wpisanego wyrazu do elementow seta?

Set, tailSet i odpowiedni Comparator.

Zysk będzie pamięciowy ;) Kolosalny tak nawiasem mówiąc.

Tak, ale tylko wersja skompresowana. Wersja, o której piszesz wcale nie musi być optymalniejsza pamięciowo.

Dziekuje za odpowiedzi.

Moj slownik ma najpierw wczytac slowa z pliku tekstowego (minimalnie 5.000 slow), a nastepnie zapisac je tablicy/liscie wraz z ich czestotliwoscia
wystepowania (obliczona na podstawie wczytanego tekstu).
Duzo slow bedzie sie pewnie powtarzac dlatego mysle ze sam slownik bedzie ich mial ok ~3.000.

Zalezy mi na jak najszybszym wyszukiwaniu, a nie dodawaniu slow takze bylbym bardziej sklonny do zastosowania tablicy (Array) a nie listy (LinkedList)..
Tylko jak napisal "Shalom", pod wzgledem pamieciowym jest to niewykonalne...
Czy moze sie myle, bo potem znowu "Shalom" napisal, ze jesli czesto bedziemy szukac slow, to ArrayList bedzie ok.
Sam juz nie wiem co teraz mam myslec...?

Struktura TRIE dalej nie jest dla mnie 100% jasna:

a) Czy strukture TRIE mozna zaimplementowac uzywajac albo ArrayList, albo LinkedList (z Java Collections)?
Jesli tak, to czy do wyszukiwania, dodawania usuwania etc... elementow (slow) wystarcza nam metody znajdujace sie w ArrayList lub LinkedList?
Czy moze bedziemy musieli te metody sami stworzyc?

b) Jak powinien wygladac kazdy nod mojego drzewa TRIE (jakie wartosci, linki etc..?)
Czy powinno to wygladac tak jak na zalaczonym ponizej obrazku?

c) Jaki bedzie schemat indeksowania (indexing scheme) dla TRIE (w przypadku 27 elementow - 26 liter + terminator oznaczajacy slowo).
Jakie cyfry powinienem wpisac jako index w przykladzie pokazanym na zalaczonym rysunku?

d) Co bedzie zawieral i jaka wartosc bedzie mial najwyzszy poziom drzewa (header)?

e) Czy ktos moze na krotkim przykladzie pokazac jak kazde slowo wczytane z pliku tekstowego bedzie wstawiane w odpowiednie miejsce drzewa TRIE?
Wiem jak to bedzie wygladac w przypadku Drzewa Binarnego (Binary Search Tree), ale jakos nie moge sobie wyobrazic jak to bedzie w przypadku TRIE.

Z gory dziekuje za poswiecony czas.

pozdrawiam

Czytaj uważnie. Pisalismy że że można to zrobic za pomocą posortowanego ArrayList, ale jednego. Bez żadnych drzew. Ot po prostu możesz binarnie szukać odpowiednich słów w tym ArrayList. To jest najłatwiejsze rozwiązanie.

Takie trie o jakim mówiłeś jest niewykonalne o czym już pisałem. Jedyna sensowna implementacja to taka na listach, gdzie dodajesz jedynie istniejące słowa. Schemat dodawania do TRIE wygląda mniej wiecej tak: Mamy puste drzewko. Dodaje do niego słowo ALA
A
|
L
|
A
|
*

Teraz dodaje słowo ALE i drzewko wygląda tak:
A
|
L
|
AE
| |
**
A jak dodam słowo ALAN to tak:
A
|
L
|
AE
/| |
N**
|
*

Proponuje zebyś jednak zrobil to łatwiejszym sposobem i użył zwykłej kolekcji do tego ;)

Moze sie powtarzam, ale nie rozumiem tego jeszcze do konca takze prosze mi jeszcze wytlumaczyc/potwierdzic nastepujace rzeczy:

Shalom napisał(a)

Czytaj uważnie. Pisalismy że że można to zrobic za pomocą posortowanego ArrayList, ale jednego. Bez żadnych drzew. Ot po prostu możesz binarnie szukać odpowiednich słów w tym ArrayList. To jest najłatwiejsze rozwiązanie.

1. Jaka bedzie zlozonosc czasowa wyrazona w O(..) takiego rozwiazania? Wydaje mi sie, ze im dluzsze slowo, tym duzo wolniejszy bedzie program?
2. Jak bedzie wygladac wyszukiwanie wyrazow? Chodzi mi o to jak mozna przedstawic wyszukiwanie w zaleznosci od 'ilosci liter' za pomoca kodu? No i tym bardziej jesli bedziemy uzywac klawiatury telefonu, gdzie 1 przycisk odpowiada 3 lub 4 literom?

Np: zeby napisac wyraz 'KOD' wciskami kolejno numer '5' , '6' i '3' na klawiaturze telefonu:
przycisk '5' = j, k, l
przycisk '6' = m, n, o
przycisk '3' = d, e, f

Czy trzeba bedzie dodawac? charAt(i), charAt(i) etc... gdzie i = 0 ; i < string.length ? zeby wyszukac odpowiednia sekwencje w slowniku? potem porownac z 'czestotliwoscia slow' i zwroci najpopularniejesze.
Bede wdzieczny za jakies wskazowki.

Shalom napisał(a)

Takie trie o jakim mówiłeś jest niewykonalne o czym już pisałem. Jedyna sensowna implementacja to taka na listach, gdzie dodajesz jedynie istniejące słowa. Schemat dodawania do TRIE wygląda mniej wiecej tak: Mamy puste drzewko. Dodaje do niego słowo ALA

Czyli mam drzewo TRIE, ktore implementuje za pomoca LinkedList z Java Collections?
Czy w takim wypadku bede potrzebowac wlasne metody zeby dodawac, wyszukiwac etc.. elementy z drzewa, czy te dostepne w kolecji LinkedList wystarcza?
Nie tworzylem nic takiego wczesniej wiec nie wiem.
Jaka bedzie zlozonosc czasowa takiego rozwiazania?

Proponuje zebyś jednak zrobil to łatwiejszym sposobem i użył zwykłej kolekcji do tego ;)

Tak dla potwierdzenia: Przez kolekcje rozumiesz ArrayList z Java Collections?

Z gory dziekuje za odpowiedz

1. Jaka bedzie zlozonosc czasowa wyrazona w O(..) takiego rozwiazania? Wydaje mi sie, ze im dluzsze slowo, tym duzo wolniejszy bedzie program?

Dużo wolniejszy? Przy wyszukiwaniu binarnym dla słownika z 5000 słów maksymalna liczba porównań (słów) będzie wynosić ~12. Nie jest to jakaś strasznie duża liczba.

1. Jak bedzie wygladac wyszukiwanie wyrazow?

Algorytm lower bound, który zamiast porównywać poszczególne litery, będzie porównywał grupy, do których należą. Oczywiście słownik musisz mieć w odpowiedni sposób posortowany, z uwzględnieniem grup liter - głównie chodzi o znaki diakrytyczne.

Szukanie binarnie to zawsze pesymistycznie O(log(2)n), więc tragedii nie ma ;)
Jeśli chodzi o używanie klawiatury komórkowej to niestety będziesz musiał wykonać kilka poszukiwań po prostu. Najlepiej zapamiętując "ślepe zaułki". Tzn ktoś wpisał
KO
przycisk '5' = j, k, l
przycisk '6' = m, n, o
wyszukujesz wszystkie kombinacje tych liter i wypisujesz tą która ma najwyższe prawdopodobieństwo celności (te twoje wartości jak często występuje) i jednocześnie zapamiętujesz pozostałe pasujące rozwiązania i fajnie byłoby też zapamiętać dla każdego z nich indeks ostatniego elementu który nie spełniał założenia. Następnie ktos wpisuje
D
przycisk '3' = d, e, f
I znów szukasz ale tym razem tylko w tym obszarze który znalazłeś wcześniej. W ten sposób przyspieszysz trochę szukanie.

Jeśli chodzi o implementacje TRIE to nie, LinkedList nie wystarczy, trzeba sporo kodu napisać samemu ;)

Dużo wolniejszy? Przy wyszukiwaniu binarnym dla słownika z 5000 słów maksymalna liczba porównań (słów) będzie wynosić ~12. Nie jest to jakaś strasznie duża liczba.

Ale w jaki sposob, uzywajac wyszukiwania binarnego, mozna wyszukac grupe elementow?
Wyszukiwanie binarne zwraca przeciez tylko jedna wartosc?
Np: Dla 'przyciskow (2=a,b,c) i (3=d,e,f) chcemy zeby wyszukiwanie zwrocilo wszystkie wyrazy tablicy rozpoczynajace sie na (a,b lub c), ktorych drugą literą jest (d,e lub f), a nie tylko jeden element.

Algorytm lower bound, który zamiast porównywać poszczególne litery, będzie porównywał grupy, do których należą. Oczywiście słownik musisz mieć w odpowiedni sposób posortowany, z uwzględnieniem grup liter - głównie chodzi o znaki diakrytyczne.

Znaki diakrytyczne moge zignorowac, chodzi tylko o umieszczenie 26 liter angielskiego alfabetu (a-z).

Jesli chodzi sortowanie, to czy dobrym pomyslem byloby podzielenie slownika na kilka tablic, ktore reprezentowaly by grupy liter? Np: tablica dla przycisku '2' reprezentowala by wyrazy rozpoczynajace sie na (A, B, C), tablica dla przycisku '3' -> (D, E, F) ..... tablica dla przycisku '9' wyrazy rozpoczynajace sie na (W, X, Y, Z)?
Ewentualnie 1 tablica, podzielona na 8 pod tablic?

Czy to przyspieszylo by wyszukiwanie?

z gory dzieki za pomoc

Shalom napisał(a)

Szukanie binarnie to zawsze pesymistycznie O(log(2)n), więc tragedii nie ma ;)
Jeśli chodzi o używanie klawiatury komórkowej to niestety będziesz musiał wykonać kilka poszukiwań po prostu. Najlepiej zapamiętując "ślepe zaułki"

No tak, ale jak moge wyszukac 'zakres' slow zaczynajacych sie np: od 'KO' uzywajac wyszukiwania binarnego? Wyszukiwanie binarne zwraca tylko 1 wartosc?
Jesli bede musial wykonac 'kilka poszukiwan' i porowac wszystkie kombinacje, to czy zlozonosc czasowa algortymu bedzie nadal O(log(2)n)?

Jeśli chodzi o implementacje TRIE to nie, LinkedList nie wystarczy, trzeba sporo kodu napisać samemu ;)

Co bedzie mialo mniejsza zlozonosc algorytmu wyrazona w O(...):

1. Implementacja TRIE za pomoca LinkedList
   czy
2. Implementacja za pomoca ArrayList z Java Collection (wlaczajac w to wszystkie operacja poszukiwania wszystkich kombinacji liter, porownywania ich etc..)?

Tzn ktoś wpisał
KO
przycisk '5' = j, k, l
przycisk '6' = m, n, o
wyszukujesz wszystkie kombinacje tych liter i wypisujesz tą która ma najwyższe prawdopodobieństwo celności (te twoje wartości jak często występuje) i jednocześnie zapamiętujesz pozostałe pasujące rozwiązania i fajnie byłoby też zapamiętać dla każdego z nich indeks ostatniego elementu który nie spełniał założenia. Następnie ktos wpisuje
D
przycisk '3' = d, e, f
I znów szukasz ale tym razem tylko w tym obszarze który znalazłeś wcześniej. W ten sposób przyspieszysz trochę szukanie.

Wszystkich kombinacji liter szesciu liter ('5' = j, k, l) i ('6' = m, n, o) bedzie 36 (wariacje z powtorzeniami).
Jednak my jestesmy zainteresowani tylko 9 kombinacjami (bo sekwencja klawiszy jest '5' + '6' czyli pierwsza litera musi byc J, K lub L a druga litera ma byc M, N lub O).
Jak zrobic zeby program nie tracil czasu i nie wyszukiwal 36 kombinacji, tylko 9 kombinacji (zgodnie z sekwencja klawiszy '5' + '6')?

A nawet jesli program wyszuka te 9 oczekiwanych przez nas kombinacji, to czas potrzebny do wyszukania kombinacji w zaleznosci od dlugosci szukanego slowa to:

Dla slowa 2 literowego program wyszukuje 33 = 9 kombinacji
Dla slowa 3 literowego program wyszukuje 93 = 27 kombinacji
Dla slowa 4 literowego program wyszukuje 273 = 81 kombinacji
Dla slowa 5 literowego program wyszukuje 813 = 243 kombinacji
Dla slowa 6 literowego program wyszukuje 243*3 = 729 kombinacji
etc...
Czyli samo wyszukanie kombinacji dla dluzszych wyrazow bardzo spowolni prace programu.
Czyli zlozonosc czasowa wyrazona w O(..) dla samej takiej operacij bedzie O(n^2) czy mam racje?
Jesli tak, to takie rozwiazanie odpada... :-/

Poprawcie mnie jesli sie myle.

pozdrawiam

Dlatego mówiłem o pewnej optymalizacji.
Wyszukujesz sobie kombinacje z 2 klawiszy (9 wyszukiwań). Oczywiście jasne jest że musisz to szukanie binarne napisać sam. Teraz połówkujesz sobie przedział i szukasz tych 2 liter które cię interesują. Zapamiętujesz też ostatnie połowienie które wrzuciło cię w obszar gdzie tych liter nie było, tzn skoczyłeś w środek przedziału i zobaczyłeś się zamiast KO jest tam KR (i następny skok zrobiłeś w lewą połówkę, bo szukasz czegoś mniejszego). Ale pozycję tego KR zapamiętałeś. Teraz kiedy dokładasz 3 literkę to nie szukasz w całej tablicy, tylko od pierwszego wystąpienia KO (to znalazłeś przed chwilą) do tego KR. To dość znacznie ogranicza obszar szukania.
Oczywiście ta implementacja szukania binarnego musisz mieć tez zaimplementowanie próbkowanie sąsiednich wyrazów, żeby było wiadomo kiedy stoimy na pierwszym wyrazie który zawiera szukane przez nas literki.

Shalom napisał(a)

Dlatego mówiłem o pewnej optymalizacji. Wyszukujesz sobie kombinacje z 2 klawiszy (9 wyszukiwań).

Jak 'wytlumaczyc' komputerowi zeby wyszukal tylko 9 z 36 mozliwych kombinacji i zeby wyszukal te 'wlasciwe 9 kombinacji?
Wiem, ze jest to zwiazane z sekwencja klawiszy i sa 4 mozliwosci (4*9=36), ale
nie wiem jako to przeniesc na kod, ktory bedzie zrozumialy dla komputera... :-/

Oczywiście jasne jest że musisz to szukanie binarne napisać sam. Teraz połówkujesz sobie przedział i szukasz tych 2 liter które cię interesują. Zapamiętujesz też ostatnie połowienie które wrzuciło cię w obszar gdzie tych liter nie było, tzn skoczyłeś w środek przedziału i zobaczyłeś się zamiast KO jest tam KR (i następny skok zrobiłeś w lewą połówkę, bo szukasz czegoś mniejszego). Ale pozycję tego KR zapamiętałeś. Teraz kiedy dokładasz 3 literkę to nie szukasz w całej tablicy, tylko od pierwszego wystąpienia KO (to znalazłeś przed chwilą) do tego KR. To dość znacznie ogranicza obszar szukania.
Oczywiście ta implementacja szukania binarnego musisz mieć tez zaimplementowanie próbkowanie sąsiednich wyrazów, żeby było wiadomo kiedy stoimy na pierwszym wyrazie który zawiera szukane przez nas literki.

Czy moglbys podac jakis link, ktore implementuje podobne wyszukiwanie binarne...?
Nigdy czegos takiego nie pisalem i pewnie bez dobrego przykladu sobie nie poradze...

Prosze jeszcze odpowiedz na to pytanie:
Co bedzie mialo mniejsza zlozonosc algorytmu wyrazona w O(...):

1. Implementacja TRIE za pomoca LinkedList
   czy
2. Implementacja za pomoca ArrayList z Java Collection (wlaczajac w to wszystkie operacja poszukiwania wszystkich kombinacji liter, porownywania ich etc..)?

pozdrawiam i dziekuje

Jak to jak? Tworzysz stringi których potem szukasz w List, to chyba oczywiste. Stringi tworzysz w czasie wciskania klawiszy więc wiadomo w jakiej kolejności są litery.
Działanie szukania binarnego jest proste ;)
Masz posortowany zbiór. Początkowy indeks to P, końcowy to Q. Pobierasz wartość elementu na środku tablica[(Q-P)/2]. Sprawdzasz czy to czego szukasz jest mniejsze czy większe od tego co wlaśnie pobrałeś. Jeśli jest mniejsze to ustawiasz że koniec Q = (Q-P)/2, bo elementy które są dalej na pewno nie spełniają wymagań.
Jeśli element szukany ejst większy to zmieniasz początek P = (Q-P)/2.

np.:
1 2 3 4 5 6 7 8 9 10
Szukamy 4
Strzelamy w środek i trafiamy na 5. 5 > 4 więc szukana liczba jest po lewej. Skracamy obszar poszukiwań:
1 2 3 4 5
Strzelamy w środek i trafiamy na 3. 3 < 4 więc szukana liczba jest po prawej. Skracamy obszar poszukiwań:
3 4 5
Strzelamy w środek i trafiamy.

Oczywiście ze TRIE bo tam czas zależy jedynie od długości wyrazu, a nie od ilości wyrazów w drzewie.

Dzieki za odpowiedz.
Sprobuje to wszystko przetrawic i zaczac cos w koncu robic :)

Jeszcze tylko jedno male pytanie:
Czy jesli mialbym to robic za pomoca drzewa TRIE, to lepiej zeby nody byly cyframi 2-9 czy literami alfabetu A-Z?

pozdrawiam

A co by ci te cyfry niby mówiły? o_O
http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg
obrazek z wikipedii moze ci coś rozjaśni :)
Nody jako takie to będą klasy, tak w ogóle ;) bo muszą przechowywać trochę więcej informacji niz tylko samą literkę (ot chocby tablicę wskazań na kolejne literki)

ok, dzieki
A te cyfry na niebiesko to jakis 'schemat indexowania' nodow?
Czy jest jakas logika w sposobie ich rozmieszczenia przy poszczegolnych nodach? Bo jak dla mnie te cyfry sa rozmieszczone losowo... :-/

pozdrawiam

Jaka bedzie zlozonosc czasowa programu implementujacego slownik T9 z uzyciem drzewa TRIE wyrazona przy uzyciu notacji Wielkie O (Big O notation)?

Najbardziej czasocholonna czesc algorytmu to chyba szukanie slow, po wczesniejszym wpisaniu sekwencji klawiszy (przedrostkow)...
Jak obliczyc taka zloznosc czasowa?

Kombinujecie.
Każdy wyraz zamieniasz na postać "cyfrową", tj. zastepujesz litery cyframi z klawiatury np.
"ala" -> "252"
"kot" -> "568"

Teraz tak zbudowanych "wyrazów" używasz do zbudowania trie (w liściach będą wszystkie wyrazy w postaci oryginalnej) albo pososrtowanej tablicy, w której bedziesz wyszukiwał binarnie. Wydaje mi się, że duża posortowana tablica będzie nieznacznie lepsza pamięciowo, jednak w obu sytuacjach i tak musisz mieć w pamięci wszystkie słowa.

W obu przypadkach wyszukiwanie danego prefiksu masz w O(log n), gdzie n liczba słów.

T9 bierze pod uwagę częstość wpisywania słów przez użytkownika, tzn w czasie zmienia się kolejność podpowiedzi, a także czasem są podpowiadane dłuższe słowa niż wynikałoby to z wciśniętych klawiszy (np bardzo często piszemy "sortować", wtedy po kilku klawiszach, np czterech, T9 podaje "sortować" jako jedną z podpowiedzi). Tutaj chyba przydałby się jakiś drzepiec.

To co za problem dorzucić jeszcze do tego jakiś licznik częstości wystąpień?

Zlozonosc programu oblicza sie dla najbardziej czasochlonnej operacji (algorytmu) w programie i wyraza przez notacje Wielkie O.
Np: jesli mamy do porownania 2 algorytmy w programie (gdzie ‘n’ to liczba elementow do przetworzenia):

1. 5 + 0.6n + 0.008n^2
2. 50 + 1000log2n

To bardziej zlozony jest pierwszy, bo m= O(n^2)
Zlozonosc drugiego jest = O(logn) czyli pracuje on szybciej.
Tak wiec na tej podstawie chce obliczyc zlozonosc mojego programu, slownika T9.

O najbardziej zlozony algortym podejrzewalem 2 elementy mojego programu:

1) Szukanie wszystkich mozliwych przedrostkow wyrazow na podstawie ilosci wcisnietych klawiszy (‘2’, ‘3’, ‘4’ etc..) gdzie ‘n’ to najdluzszy mozliwy wyraz w drzewie

Moj algortym wyszukuje wszystkie mozliwe przedrostki wyrazow na podstawie ilosci wcisnietych klawiszy (‘2’, ‘6’, ‘8’ etc..)
Czyli np: dla wcisnietego jednego klawisza k=1 , program generuje 3^1 = 3 przedrostki
Dla wcisnietych dwoch klawiszy k= 2, program generuje 3^2 = 9 przedrostow.
Klawiszy z literkami na klawiaturze telefonu mamy 8 , a wszystkich liter 26, tak wiec na kazdy klawisz przypada srednio 3,25 literki.
Jesli np: najdluzszy wyraz w drzewie ma ‘n’ liter, to w najgorszym wypadku trzeba bedzie wygenerowac (3,25)^n przedrostkow.
Chcac wyrazic to za pomoca notacji Wielkie O, bedziemy meli O( (3,25)^n ) czyli zlozonosc wykladnicza, najgorsza z mozliwych...
Czy mam racje?
Tyle ze ta zloznosc w przypadku mojego programu jest do zaakceptowania, bo pomimo iz jest wykladnicza, nie bedzie rosla w nieskonczonosc (n, czyli najdluzszy wyraz w drzewie bedzie mial powiedzmy 20-25 liter).
Czy mam racje?</span>

2) Wyszukiwanie wyrazow w drzewie Trie dla danego prefixu , gdzie ‘n’ to najdluzszy mozliwy wyraz wystepujacy w drzewie:

Tu rozloze to na dwie czesci
a) Najpierw musimy dojsc do ostatniej litery prefiksu (zeby zwrocic wyrazy, ktore zaczynaja sie od tego prefixu).
W najgorszym wypadku bedzie to ‘k’*’a’, gdzie ‘k’ to dlugosc stringa, a ‘a’ to liczba liter angielskiego alfabetu
b) Do tego musimy dodac zlozonosc przeszukiawnia drzewa w dol od ostatniej litery prefiksu, czyli:
( (‘n’-‘k’) * ‘a’), gdzie ‘n’ do dlugosc najdluzszego wyrazu, ‘k’ to dlugosc aktualnego stringa, a ‘a’ to liczba liter angielskiego alfabetu,

Dodajac wartosci a) i b), uzyskujemy maksymalna zlozonosc dla wyszukania wszystkich wyrazow z drzewa z okreslonym prefiksem:
(k*a) + ((n-k) a)
Wyrazone w notacji Wielkie O przez O( (ka) + ((n-k)*a )</span>

A teraz obliczajac na konkretnym przykladzie:
‘a’ = 26 (liczba liter angielskiego alfabetu)
‘n’ = 10 (najdluzszy wyraz w drzewie)
‘k’ = 8 (dlugosc aktualnie wyszukiwanego stringa)

Dla szukania wszystkich mozliwych przedrostkow: (3,25)^8 = 12447

Dla wyszukania wszystkich wyrazow dla danego prefiksu: (8*26) + ((10-8)*26) = 208 + 52 = 260

Z tego wynika, ze wyszukiwanie zloznosc mojego programu to O(3,25^n), czyli rosnie wykladniczo ale... jej wzrost jest ograniczony najdluzszym wyrazem w drzewie, tak wiec nie jest taki najgorszy.

Prosze napiszcie czy to co napisalem powyzej ma sens i czy sie z tym zgadzacie.

Z gory dziekuje za pomoc

Fajnie gdyby jeszcze ktos mogl napisac dlaczego ponizsze struktury danych sa gorsze do implementacji slownika T9 niz struktura drzewa TRIE? :

Po czesci sam na te pytania odpowiedzialem (w 1 poscie, ale nikt mi nie potwierdzil/zaprzeczyl)?
Wytlumaczenie prostym jezykiem mile widziane :)

@greep, jakbyś przeczytał mojego posta, to byś zobaczył, że cały Twój sposób jest głupi. Nie trzeba generować żadnych wszystkich możliwych przedrostków, a algorytm ma złożoność O(log n) na każde naciśnięcie klawisza. BTW: O(3^n) jest zwykle niepraktyczne już od n w okolicach 6-10 (w zależności od szybkości sprzętu i stałej), więc do 20-25 jeszcze bardzo daleko.

Jeśli program działa szybciej niż użytkownik jest w stanie wklepywać literki, to głęboka analiza algorytmu i jego złożoności obliczeniowej jest tylko stratą czasu.

Krolik napisał(a)

@greep, jakbyś przeczytał mojego posta, to byś zobaczył, że cały Twój sposób jest głupi. Nie trzeba generować żadnych wszystkich możliwych przedrostków, a algorytm ma złożoność O(log n) na każde naciśnięcie klawisza. BTW: O(3^n) jest zwykle niepraktyczne już od n w okolicach 6-10 (w zależności od szybkości sprzętu i stałej), więc do 20-25 jeszcze bardzo daleko.

Nie moge zrozumiec dlaczego twiedzisz, ze moj algorytm ma zlozonosc O(log n)???
Bede wdzieczny za wytlumaczenie.
Moze chodzi Ci o to, ze tym Twoim sposobem bedzie mial O(log n)?
Moj program generuje wszystkie przedrostki. Ponizej wstawiam rekursywna metode, ktora to robi, znaczy odwoluje sie do siebie zeby laczyc wszystkie mozliwe kombinacje liter z wcisnietych klawiszy.
A cos co jest rekursywane raczej ma wieksza zlozonosc algorytmu niz O(log n), prawda?

Metoda:
149 private static Collection<String> lettersCombinations(int n, String prefix, List<String> list) {
150 if (_keys.size() > 0) {
151 List<Character> chars = _keyMap.get(_keys.get(n));
152
153 for (int i = 0; i < chars.size(); i++) {
154 char c = chars.get(i);
155
156 if (n + 1 < _keys.size()) {
157 lettersCombinations(n + 1, prefix + c, list);
158 }
159 else {
160 list.add(prefix + c);
161 }
162 }
163 }
164
165 return list;
166 }

Azarien napisał(a)

Jeśli program działa szybciej niż użytkownik jest w stanie wklepywać literki, to głęboka analiza algorytmu i jego złożoności obliczeniowej jest tylko stratą czasu.

I wlasnie w swoim programie odkrylem, ze przy wpisaniu wiecej niz 12 liter, program bardzo spowalania.
Wtedy tez wyskakuje blad: "Out of Memory Java Heap Space" (link do zrzutu z ekranu ponizej) .
Blad jak widac na screenie wyskakuje przy dzialaniu powyzszej metody letterCombinations.
Takze to chyba 100% dowod ze program dziala ze zlozonoscia 3^n, prawda?

http://ScrnSht.com/kazmdn

Tylko ze znowu uznalbym to za akceptowalne, gdyz najdluzsze slowo w slowniku ma 17 znakow.
Slow ze znakami od 12-17 jest bardzo malo takze uzytkownik po wcisnieciu juz kilku klawiszy (max. 7-8) bedzie mial na liscie tylko jedno pasujace slowo. Nie bedzie wiec potrzeby aby dalej obciazac program, szukajac dalszych kombinacji, skoro jedyne slowo zostalo znalezione juz wczesniej i mozna bylo je dodac do tekstu. Mam racje?

bede wdzieczny za jakies potwierdzenie ostatniego posta.