Алгоритм группировки слов анаграммы

Question

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

ввод:

man car kile arc none like

выход:

man
car arc
kile like
none

Лучшее решение, которое я сейчас разрабатываю, основано на хеш-таблице, но я думаю об уравнении для преобразования слова анаграммы в целочисленное значение.

Пример: man => 'm' + 'a' + 'n', но это не даст уникальных значений.

Есть предложения?

---

См. Следующий код в C #:

string line = Console.ReadLine();
string []words=line.Split(' ');
int[] numbers = GetUniqueInts(words);
for (int i = 0; i < words.Length; i++)
{
    if (table.ContainsKey(numbers[i]))
    {
        table[numbers[i]] = table[numbers[i]].Append(words[i]);
    }
    else
    {
        table.Add(numbers[i],new StringBuilder(words[i]));
    }

}

Проблема в том, как разработать GetUniqueInts(string []) метод.

Answer 1

Не беспокойтесь о пользовательской хэш-функции. Используйте обычную строковую хеш-функцию на любой платформе. Важно сделать ключ для вашей хеш-таблицы идеей «отсортированного слова» - где слово сортируется по буквам, поэтому «car» => «acr» Все анаграммы будут иметь одно и то же «отсортированное слово».

Просто добавьте хеш от "отсортированного слова" к "списку слов для этого отсортированного слова". В LINQ это невероятно просто:

using System;
using System.Collections.Generic;
using System.Linq;

class FindAnagrams
{
    static void Main(string[] args)
    {
        var lookup = args.ToLookup(word => SortLetters(word));

        foreach (var entry in lookup)
        {
            foreach (var word in entry)
            {
                Console.Write(word);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
    }

    static string SortLetters(string original)
    {
        char[] letters = original.ToCharArray();
        Array.Sort(letters);
        return new string(letters);
    }
}

Пример использования:

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like
man
car arc
kile like
none

Answer 2

Я использовал схему, вдохновленную Годелем:

Назначьте простые буквы от P_1 до P_26 (в любом порядке, но для получения небольших хэш-значений лучше всего давать обычные буквы небольшими простыми числами).

Построена гистограмма букв в слове.

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

Код Python:

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53]


def get_frequency_map(word):
    map = {}

    for letter in word:
        map[letter] = map.get(letter, 0) + 1

    return map


def hash(word):
    map = get_frequency_map(word)
    product = 1
    for letter in map.iterkeys():
        product = product * primes[ord(letter)-97] ** map.get(letter, 0)
    return product

Это умно превращает сложную задачу поиска поданаграмм в (также известную как сложную) задачу факторизации больших чисел ...

Answer 3

версия Python для хихиканья:

from collections import defaultdict
res = defaultdict(list)
L = "car, acr, bat, tab, get, cat".split(", ")

for w in L:
    res["".join(sorted(w))].append(w)

print(res.values())

Answer 4

Вам понадобятся большие целые числа (или битовый вектор), но может сработать следующее

первое вхождение каждой буквы получает номер бита для этой буквы, второй случай получает номер бита для этой буквы + 26.

Например

a # 1 = 1 б № 1 = 2 с # 1 = 4 # 2 = 2 ^ 26 b # 2 = 2 ^ 27

Затем вы можете сложить их вместе, чтобы получить уникальное значение слова на основе его букв.

Ваши требования к хранению значений слов будут:

n * 26 бит

где n - максимальное количество повторений любой повторяющейся буквы.

Answer 5

Не думаю, что вы найдете что-то лучше хеш-таблицы с пользовательской хеш-функцией (которая сортирует буквы слова перед хэшированием).

Сумма букв никогда не сработает, потому что вы не можете по-разному различать 'ac' и 'bb'.

Answer 6

Я бы не использовал хеширование, поскольку это добавляет дополнительную сложность для поиска и добавляет. Хеширование, сортировка и умножение будут происходить медленнее, чем простое решение на основе гистограмм на основе массива с уникальным отслеживанием. В худшем случае O (2n):

// structured for clarity
static bool isAnagram(String s1, String s2)
{
    int[] histogram = new int[256];

    int uniques = 0;

    // scan first string
    foreach (int c in s1)
    {
        // count occurrence
        int count = ++histogram[c];

        // count uniques
        if (count == 1)
        {
            ++uniques;
        }
    }

    // scan second string
    foreach (int c in s2)
    {
        // reverse count occurrence
        int count = --histogram[c];

        // reverse count uniques
        if (count == 0)
        {
            --uniques;
        }
        else if (count < 0) // trivial reject of longer strings or more occurrences
        {
            return false;
        }
    }

    // final histogram unique count should be 0
    return (uniques == 0);
}

Answer 7

Назначьте уникальное простое число буквам a-z

Итерируйте массив слов, создавая произведение простых чисел на основе букв в каждом слове.
Сохраните этот продукт в вашем списке слов с соответствующим словом.

Сортировать массив по возрастанию по продукту.

Итерируйте массив, делая контрольный перерыв при каждом изменении продукта.

Answer 8

Я реализовал это раньше с помощью простого массива букв, например ::1001

unsigned char letter_frequency[26];

Затем сохраните это в таблице базы данных вместе с каждым словом. Слова с одинаковой частотой букв «сигнатура» являются анаграммами, и простой запрос SQL возвращает все анаграммы слова напрямую.

С некоторыми экспериментами с очень большим словарем, я не нашел ни одного слова, которое превышало бы частоту 9 для любой буквы, поэтому «подпись» может быть представлена ​​в виде строки чисел 0..9 разделить пополам, упаковав в байты как шестнадцатеричный код, и еще больше уменьшив двоичным кодированием числа, но пока я не беспокоился об этом).

Вот функция ruby, которая вычисляет подпись данного слова и сохраняет его в хэше, исключая дубликаты. Из хэша я позже создаю таблицу SQL:

def processword(word, downcase)
  word.chomp!
  word.squeeze!(" ") 
  word.chomp!(" ")
  if (downcase)
    word.downcase!
  end
  if ($dict[word]==nil) 
    stdword=word.downcase
    signature=$letters.collect {|letter| stdword.count(letter)}
    signature.each do |cnt|
      if (cnt>9)
        puts "Signature overflow:#{word}|#{signature}|#{cnt}"
      end
    end
    $dict[word]=[$wordid,signature]
    $wordid=$wordid+1
  end
end

Answer 9

код питона:

line = "man car kile arc none like"
hmap = {}
for w in line.split():
  ws = ''.join(sorted(w))
  try:
    hmap[ws].append(w)
  except KeyError:
    hmap[ws] = [w]

for i in hmap:
   print hmap[i]

выход:

['car', 'arc']
['kile', 'like']
['none']
['man']

Answer 10

Просто хочу добавить простое решение Python в дополнение к другим полезным ответам:

def check_permutation_group(word_list):
    result = {}

    for word in word_list:
        hash_arr_for_word = [0] * 128  # assuming standard ascii

        for char in word:
            char_int = ord(char)
            hash_arr_for_word[char_int] += 1

        hash_for_word = ''.join(str(item) for item in hash_arr_for_word)

        if not result.get(hash_for_word, None):
            result[str(hash_for_word)] = [word]
        else:
            result[str(hash_for_word)] += [word]

return list(result.values())