Mam długą listę słów i chcę pokazać słowa zaczynające się od tekstu wprowadzonego przez użytkownika. Gdy użytkownik wprowadzi znak, aplikacja powinna zaktualizować listę wyświetlaną użytkownikowi. Powinien być jak AutoCompleteTextView na Androida. Ciekawi mnie tylko najlepsza struktura danych do przechowywania słów, aby wyszukiwanie było bardzo szybkie.Jaka jest najlepsza struktura danych do automatycznego uzupełniania tekstu?
Można użyć tria. http://en.wikipedia.org/wiki/Triehttps://stackoverflow.com/search?q=trie
Miły artykuł - http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/
PS: Jeśli masz jakieś podrzędne sekwencje, które „nie rozgałęzia”, a następnie można zaoszczędzić miejsce przy użyciu Trie radix, który jest wdrożenie trie, które stawia kilka znaków w węźle, gdy to możliwe - http://en.wikipedia.org/wiki/Radix_tree
można znaleźć ten wątek interesujący:
Nie jest to dokładnie to, czego potrzebujesz, zamiast tego jest to nieco rozszerzona wersja twojego problemu.
Dla realizacji funkcji autouzupełniania, używane potrójne drzewa wyszukiwania (TST) są również:
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
Jednakże, jeśli chcesz znaleźć żadnej losowy fragment ciągu sznurku, spróbuj uogólnionego drzewo przyrostek.
Próbuje (i ich różne odmiany) są tutaj przydatny. Bardziej szczegółowe traktowanie na ten temat jest w tym paper. Może możesz zaimplementować procedurę realizacji dla Androida?
Myślę, że tabela hash byłaby najlepsza. Nie jestem pewien języka ani platformy, z której korzystasz, więc ogólnie tablice hash są szybkie i dynamiczne. – c0d3Junk13
cóż ... najpierw musimy znać platformę, z którą pracujesz. Android? iOS? Windows? Linux? OSX? Internet lub HTML? –
@ c0d3Junk13 Jak wyszukiwałbyś ciągi z danym prefiksem w tablicy hashtable? – delnan