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

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 b #1 = 2 C#1 = 4 a #2 = 2^26 b #2 = 2 ^ 27

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

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

n * 26 бит

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

Answer 5

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

Сумма букв никогда не сработает, потому что вы не можете сделать "a c" и "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

Присвойте уникальное простое число буквам az

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

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

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

Answer 8

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

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

Анаграммы можно найти следующим образом:

1. Длина слова должна совпадать.
2. Выполните сложение каждого символа в терминах целочисленных значений. Эта сумма будет соответствовать, если вы выполните то же самое на анаграмме.
3. Выполните умножение каждого символа в терминах целочисленных значений. Оцененное значение будет соответствовать, если вы выполните то же самое на анаграмме.

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

---

Пример: abc cba

Длина обоих слов 3.

Сумма отдельных символов для обоих слов составляет 294.

Продукт отдельных символов для обоих слов - 941094.

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())

Answer 11

Код Python:

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 12

Я сгенерирую hasmap на основе примера слова и остальных алфавитов, которые меня не волнуют.

Например, если слово "car", моя хеш-таблица будет выглядеть следующим образом: a,0 b,MAX c,1 d,MAX e,MAX ... .. r,2 . В результате любой, имеющий больше 3, будет считаться не соответствующим

(дополнительная настройка...) И мой метод сравнения будет сравнивать сумму хеша в самом вычислении хеша. Это не будет продолжаться, как только он сможет определить, что слово не равно.

public static HashMap<String, Integer> getHashMap(String word) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        String[] chars = word.split("");
        int index = 0;
        for (String c : chars) {
            map.put(c, index);
            index++;
        }
        return map;
    }

    public static int alphaHash(String word, int base,
            HashMap<String, Integer> map) {
        String[] chars = word.split("");
        int result = 0;
        for (String c : chars) {
            if (c.length() <= 0 || c.equals(null)) {
                continue;
            }
            int index = 0;
            if (map.containsKey(c)) {
                index = map.get(c);
            } else {
                index = Integer.MAX_VALUE;
            }
            result += index;
            if (result > base) {
                return result;
            }
        }
        return result;
    }

Основной метод

  HashMap<String, Integer> map = getHashMap(sample);
        int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map);
        for (String s : args) {
                if (sampleHash == alphaHash(s, sampleHash, map)) {
                    System.out.print(s + " ");
                }
            }

Answer 13

В C я только что реализовал следующий хеш, который в основном выполняет 26-битную битовую маску на предмет того, содержит ли слово в словаре определенную букву. Итак, все анаграммы имеют одинаковый хэш. Хеш не учитывает повторяющиеся буквы, поэтому будет некоторая дополнительная перегрузка, но все же он будет быстрее, чем моя реализация perl.

#define BUCKETS 49999

struct bucket {
    char *word;
    struct bucket *next;
};

static struct bucket hash_table[BUCKETS];

static unsigned int hash_word(char *word)
{
    char *p = word;
    unsigned int hash = 0;

    while (*p) {
        if (*p < 97 || *p > 122) {
            return 0;
        }
        hash |= 2 << (*p - 97);
        *p++;
    }

    return hash % BUCKETS;
}

Перегруженные сегменты создаются и добавляются в виде связанного списка и т. Д. Затем просто напишите функцию, которая гарантирует, что слова, соответствующие значению хеш-функции, имеют одинаковую длину, а буквы в каждом из них имеют значения от 1 до 1 и возвращают их как совпадающие.

Answer 14

Версия JavaScript. используя хеширование.

Сложность времени: 0(нм), где n - количество слов, m - длина слова.

var words = 'cat act mac tac ten cam net'.split(' '),
    hashMap = {};

words.forEach(function(w){
    w = w.split('').sort().join('');
    hashMap[w] = (hashMap[w]|0) + 1;
});

function print(obj,key){ 
    console.log(key, obj[key]);
}

Object.keys(hashMap).forEach(print.bind(null,hashMap))