Wyszukiwarka słów Scrabble:budowanie trie, przechowywanie trie, używanie trie?

Najpierw spójrzmy na ograniczenia problemu. Chcesz przechowywać listę słów dla gry w strukturze danych, która skutecznie obsługuje problem „anagramu”. To znaczy, biorąc pod uwagę „stelaż” składający się z n liter, jakie są wszystkie n lub mniej-literowe słowa z listy słów, które można utworzyć z tego stojaka. lista słów będzie zawierała około 400 000 słów, a więc prawdopodobnie od jednej do dziesięciu megabajtów danych po rozpakowaniu.

Trie to klasyczna struktura danych używana do rozwiązania tego problemu, ponieważ łączy ona zarówno wydajność pamięci, jak i wydajność wyszukiwania. Mając listę słów zawierającą około 400 000 słów o rozsądnej długości, powinieneś być w stanie zachować tę próbę w pamięci. (W przeciwieństwie do rozwiązania typu b-drzewa, w którym większość drzewa jest przechowywana na dysku, ponieważ jest zbyt duże, aby zmieścić się w całej pamięci jednocześnie.)

Trie to w zasadzie nic innego jak drzewo 26-arowe (zakładając, że używasz alfabetu rzymskiego), w którym każdy węzeł ma literę i jeden dodatkowy bit na każdym węźle, który mówi, czy jest to koniec słowa.

Naszkicujmy więc strukturę danych:

class TrieNode
{
    char Letter;
    bool IsEndOfWord;
    List<TrieNode> children; 
}

To oczywiście tylko szkic; prawdopodobnie chciałbyś, aby miały one odpowiednie akcesory i konstruktory właściwości i tak dalej. Może też płaska lista nie jest najlepszą strukturą danych; może jakiś słownik jest lepszy. Radzę najpierw sprawić, by działał, a następnie zmierzyć jego wydajność, a jeśli jest to nie do przyjęcia, poeksperymentować z wprowadzaniem zmian, aby poprawić jego wydajność.

Możesz zacząć od pustej próby:

TrieNode root = new TrieNode('^', false, new List<TrieNode>());

Oznacza to, że jest to „główny” węzeł trie, który reprezentuje początek słowa.

Jak dodać słowo „AA”, pierwsze słowo w słowniku Scrabble? Cóż, najpierw utwórz węzeł dla pierwszej litery:

root.Children.Add('A', false, new List<TrieNode>());

OK, nasza próba jest teraz

^
|
A

Teraz dodaj węzeł dla drugiej litery:

root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));

Nasza próba jest teraz

^
|
A
|
A$   -- we notate the end of word flag with $

Świetny. Załóżmy teraz, że chcemy dodać AB. Mamy już węzeł dla „A”, więc dodaj do niego węzeł „B$”:

root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());

a teraz mamy

    ^
    |
    A
   / \
  A$   B$

Idź tak dalej. Oczywiście, zamiast pisać „root.Children[0]...”, napiszesz pętlę, która przeszukuje próbkę, aby zobaczyć, czy żądany węzeł istnieje, a jeśli nie, utwórz go.

Aby zapisać twoją wersję na dysku — szczerze, po prostu zapisałbym listę słów jako zwykły plik tekstowy i odbudowałbym wersję, kiedy zajdzie taka potrzeba. Nie powinno to zająć więcej niż 30 sekund, a następnie możesz ponownie użyć próby w pamięci. Jeśli chcesz przechowywać trie w jakimś formacie, który jest bardziej podobny do trie, nie powinno być trudno wymyślić format serializacji.

Aby przeszukać próbę w celu dopasowania stojaka, pomysł polega na zbadaniu każdej części próby, ale przycinanie obszarów, do których stojak nie może pasować. Jeśli nie masz żadnych „A” na stojaku, nie ma potrzeby wchodzenia w żaden węzeł „A”. W poprzednim pytaniu naszkicowałem algorytm wyszukiwania.

Mam implementację trwałej próby w stylu funkcjonalnym, o której chciałem pisać na blogu od jakiegoś czasu, ale nigdy się do tego nie udało. Jeśli w końcu to opublikuję, zaktualizuję to pytanie.