Поиск анагарам словарных слов

Question

Как я могу взять входное слово (или последовательность букв) и выводить слово из словаря, содержащего именно эти буквы?

Имеет ли java английский словарь (список слов), который я могу использовать, или существуют ли реализации этого типа с открытым исходным кодом?

Как я могу оптимизировать свой код, если это необходимо сделать повторно?

Answer 1

Конвертировать словарь в anagram dictionary. В словаре анаграмм слова индексируются своими буквами в отсортированном алфавитном порядке. Чтобы найти анаграммы для определенного слова, вы сортируете его буквы и просматриваете соответствующие слова из словаря анаграмм.

Answer 2

Два слова называются анаграммы, если они имеют те же буквы, точно такой же номер раз.

Проверка на анаграммы для сортировки писем обоих слов и проверить равенство:

sort_letters(word1) == sort_letters(word2) 

Теперь, чтобы найти все анаграммы данного словаря слово сказать word1, я хотел бы найти все слова словарь, для которого выполняется вышеуказанный тест. Чтобы оптимизировать поиск, мы можем просто найти слова из такой же длины.

Если мы должны сделать это несколько раз лучше, чтобы сделать некоторые предобработки. Мы можем построить что-то вроде HashMap, где мы бы нарисовали string набор strings, который является анаграммами. Что-то вроде:

Bad ==> Dab 
Cat ==> Act, Tac 
..... 

Теперь дано любое слово я могу посмотреть в hashMap, чтобы получить все свои анаграммы.

Answer 3

Вы можете использовать Anagrams2 example с сайта Sun в качестве отправной точки

Для повышения производительности, вы можете иметь кэш анаграмм для часто используемых/недавно использованных words.Consider с использованием WeakHashMap для этой цели

Answer 4

Как unicornaddict Вы можете довольно легко определить, являются ли два слова анаграммами путем сортировки, однако это неэффективно, особенно если вы делаете это повторно.

Готовый хеш-стол, вероятно, будет лучшим решением, загрузив в него словарь в начале программы. Довольно простой в записи алгоритма хеширования/сравнения будет

uint HashSomeWord(string someWord) 
{ 
    uint hashVal = 0; 
    //foreach letter in someword 
    { 
     //hashVal += letter.ValueAsInteger 
    } 
    return hashVal; 
} 

затем

bool IsAnagram(string inputWord, string compareTo) 
{ 
    if(inputWord == null 
     || compareTo == null 
     || inputWord.Length != compareTo.Length 
     || HashSomeWord(inputWord) != HashSomeSome(compareTo)) 
    { 
     return false; 
    } 
    if(sort_letters(inputWord) == sort_letters(compareTo)) 
    { 
     return true; 
    } 
} 

Мои Java довольно ржавый, но я думаю, что бы это сделать.

Answer 5

Из моего POV ключом к этому назначению является поиск функции (hashFunc), которая отображает строки в числа, чтобы 1) две анаграммы были сопоставлены с одним и тем же номером, 2) две неанаграммы сопоставлялись с разными номерами ,После того, как функция найдена, она может быть просто применяется к вводам, таким образом, избегая утомительных сравнение строк:

if(hashFunc(word1) == hashFunc(word2)) -> word2 is anagram of word1  

ли Java имеет английский словарь класс (список слов), которые я могу использовать, или находятся там с открытым исходным кодом реализации этого?

В системах Unix, вы можете начать с words file

Как оптимизировать свой код, если это должно быть сделано несколько раз?

Превратите словарь в хеш-таблицу, используя предварительно просчитанный hashFunc.