jak wyszukać dane słowo z ogromnej bazy danych?

Jaka jest najskuteczniejsza metoda wyszukiwania wyrazów z bazy słownika. Szukałem odpowiedzi, a ludzie zasugerowali wykorzystanie struktury danych Trie. Ale strategia tworzenia drzewa dla ogromnej ilości słów byłaby wczytywaniem podstawowej pamięci. Próbuję stworzyć aplikację dla systemu Android, która obejmuje tę implementację dla mojego projektu struktury danych. Czy ktoś mógłby mi powiedzieć, jak działa słownik.jak wyszukać dane słowo z ogromnej bazy danych?

Nawet jeśli używam słownika t9 w moim telefonie, sugestie słów pojawiają się bardzo szybko na ekranie. Ciekawy znać algorytm i projekt za nim.

Źródło

2013-03-19 Ashwin Surana

Może to być pomocne w poznaniu T9 [jak działa T9] (http://stackoverflow.com/questions/2574016/data-structure-behind-t9-type-of-dictionary) –

@MukulGoel Thanx. okazało się, że twój link jest pomocny. Ale jeszcze do przetestowania, czy będę w stanie go wdrożyć .. Nadal nauczyłem się czegoś nowego od tego ..Thanx :) –

próbowałeś słownik drzewa .. – Anshul

Możesz użyć Trie, który jest najbardziej przydatny do wyszukiwania dużych słowników. Ponieważ zbyt wiele słów korzysta z podobnego uruchamiania, trie brgins wokół stałego wyszukiwania czynników również można użyć w miejscu, z ograniczoną liczbą dostępu do pamięci fizycznej. Możesz znaleźć wiele realizacji w web.

Jeśli ktoś nie jest zaznajomiony z trie, myślę this strona jest dobra, a ja tylko cytowanie ich próbkę tutaj:

A Trie (od wydobycia), jest multi-way drzewo struktura przydatna przechowywanie ciągów przez alfabet. Służy do przechowywania dużych słowników języka angielskiego (powiedzmy) w programach sprawdzających pisownię i w programach "rozumienia" języka naturalnego. Biorąc pod uwagę dane:
an, ant, all, allot, alloy, aloe, are, ate, be 
odpowiedni trie byłoby:

To dobra praktyczna realizacja Trie w Java: http://code.google.com/p/google-collections/issues/detail?id=5

Źródło

2013-03-19 09:05:27

Ale stworzenie zestawu 10 000 słów może być problemem w aplikacji na Androida, o czym wspomniałem w moim pytaniu. No cóż, moi przyjaciele powiedzieli, że ładowanie trie na te wiele słów sprawi, że telefon komórkowy wymusi zamknięcie aplikacji: | .. –

@AcesSmart, Przede wszystkim powiedziałeś, że twój przyjaciel zaproponował ci użycie "drzewa", ale po godzinie, gdy zobaczysz odpowiedź i komentarze, zmieniłeś ją na "trie", jest to oszukiwanie i nowe pytanie. Również dlatego, że nie jesteś zaznajomiony z "trie", myślisz tak, to jest to, co działa wszędzie, jest zbyt małe niż twoje podejście "drzewo" przyjaciela, jak powiedziałem w mojej odpowiedzi możesz go użyć "na miejscu", oznacza bez ładowania w pamięci wiele wyszukiwarek korzysta z "trie" i wydaje się, że jesteś pierwszym na świecie, który mówi, że nie ma zastosowania w Twojej aplikacji mobilnej. –

Także, jeśli twoje pytanie miało kilka słów, ponieważ wspomniałeś, że twój przyjaciel sugerował podejście "drzewo", ale w przypadku, gdy zasugerował podejście "trie" i wciąż masz pytanie, to jest zabawne pytanie, jestem prawie pewien, że nie przetestowałem tego. (pamiętaj, że twoja edycja jest dostępna w historii, więc nie możesz całkowicie zmienić swojego pytania, to powoduje również wiele zmian dla czytelnika mojej odpowiedzi, oni powiedzą, dlaczego odpowiedziałem w ten sposób na to pytanie, ale możesz zadać nowe pytanie) –

Istnieje wiele sposobów, aby to zrobić. Ten, którego użyłem jakiś czas temu (co jest szczególnie dobre, jeśli nie wprowadzasz zmian w słowniku), polega na utworzeniu indeksu przedrostka.

To znaczy, że sortujesz swoje wpisy leksykologicznie. Następnie zapiszesz (koniec) pozycje zakresów dla różnych pierwszych liter. Oznacza to, że jeśli twoje wpisy mają indeksy od 1 do 1000, a słowa "aardvark - azerbejdżan" przyjmują zakres od 1 do 200, wpisujesz w oddzielnej tabeli "a | 200", to robisz to samo dla pierwszego i drugie litery. Następnie, jeśli chcesz znaleźć konkretne słowo, znacznie zmniejszyć zakres wyszukiwania. W moim przypadku indeks pierwszych dwóch liter był całkiem wystarczający.

Ta metoda wymaga również użycia DB, takiego jak SQLite, który moim zdaniem jest obecny na Androidzie.

Źródło

2013-03-19 09:06:56 Ibolit

-1

Używanie trieta jest rzeczywiście kosmiczne, po prostu zrealizowane, gdy sprawdziłem użycie pamięci RAM po załadowaniu 150 000 słów do trie, użycie wyniosło 150 MB (Trie zostało zaimplementowane w C++). Zużycie pamięci było ogromnie ze względu na wskaźniki. Skończyło się na próbach trójskładnikowych, które miały bardzo mniej strat pamięci wynoszących około 30 MB (w porównaniu do 150 MB), ale złożoność czasu wzrosła nieco. Inną opcją jest użycie "Left child Right sibling", w którym jest znacznie mniej marnotrawstwa pamięci, ale złożoność czasu jest większa niż w przypadku Ternariego Trie.

Źródło

2013-08-13 18:46:51

jak wyszukać dane słowo z ogromnej bazy danych?

Odpowiedz

Powiązane problemy