Първо, нека разгледаме ограниченията на проблема. Искате да съхраните списък с думи за игра в структура от данни, която ефективно поддържа проблема "анаграма". Тоест, като се има предвид „рафт“ от n букви, какви са всички думи с n или по-малко букви в списъка с думи, които могат да бъдат направени от този багажник. списъкът с думи ще бъде около 400 000 думи и вероятно е около един до десет мегабайта низови данни, когато е некомпресиран.
Trie е класическата структура от данни, използвана за решаване на този проблем, тъй като съчетава ефективността на паметта и ефективността на търсенето. Със списък с думи от около 400 000 думи с разумна дължина би трябвало да можете да запазите опита в паметта. (За разлика от решението от типа b-дърво, при което държите по-голямата част от дървото на диск, защото е твърде голямо, за да се побере в паметта наведнъж.)
Опитът по същество не е нищо повече от 26-арично дърво (ако приемем, че използвате латинската азбука), където всеки възел има буква и един допълнителен бит на всеки възел, който казва дали това е краят на думата.
Така че нека скицираме структурата на данните:
class TrieNode{ char Letter; bool IsEndOfWord; List деца; } Това разбира се е само скица; вероятно бихте искали да ги направите да имат подходящи средства за достъп и конструктори и какво ли още не. Също така, може би плоският списък не е най-добрата структура от данни; може би някакъв речник е по-добър. Моят съвет е първо да го накарате да работи и след това да измерите неговата производителност и ако е неприемливо, тогава експериментирайте с извършване на промени, за да подобрите неговата производителност.
Можете да започнете с празен опит:
TrieNode root =new TrieNode('^', false, new List()); Тоест, това е "корен" възел на trie, който представлява началото на дума.
Как добавяте думата "AA", първата дума в речника на Scrabble? Е, първо направете възел за първата буква:
root.Children.Add('A', false, new List()); Добре, нашият опит е сега
^|A Сега добавете възел за втората буква:
root.Children[0].Children.Add(new trieNode('A', true, new List())); Нашият опит е сега
^|A|A$ -- отбелязваме края на флага на думата с $ Страхотен. Сега да предположим, че искаме да добавим AB. Вече имаме възел за "A", така че добавете към него възел "B$":
root.Children[0].Children.Add(new trieNode('B', true, new List()); и сега имаме
<предварителен код> ^ | A / \ A$ B$Продължавай така. Разбира се, вместо да пишете „root.Children[0]...“, вие ще напишете цикъл, който търси опита, за да види дали желаният възел съществува, и ако не, създайте го.
За да съхраня вашия опит на диск - честно казано, просто бих съхранил списъка с думи като обикновен текстов файл и бих възстановил опита, когато имате нужда. Това не трябва да отнеме повече от 30 секунди и след това можете да използвате повторно опита в паметта. Ако искате да съхраните trie в някакъв формат, който прилича повече на trie, не би трябвало да е трудно да излезете с формат за сериализиране.
За да търсите в опита за съвпадение на багажник, идеята е да проучите всяка част от опита, но да отрежете областите, където багажникът не може да съвпадне. Ако нямате никакви "А" на багажника, няма нужда да слизате надолу по който и да е "А" възел. Очертах алгоритъма за търсене в предишния ви въпрос.
Имам реализация на постоянен опит във функционален стил, за който имах намерение да пиша в блог от известно време, но така и не стигнах до него. Ако евентуално го публикувам, ще актуализирам този въпрос.
