Нахождение anagaram (s) слов словаря

Как упоминалось в 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 довольно ржавая, но я думаю, что это сработает.

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

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

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

] В системах unix вы можете начать с файла слов

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

Превратить словарь в хеш-таблицу с помощью предварительно вычисленного hashFunc .

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

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

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

Проверка анаграммы заключается в сортировке букв обоих слов и проверке равенства:

sort_letters(word1) == sort_letters(word2)

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

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

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

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