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

Ответ 1

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

Просто введите хэш из "отсортированного слова" в "список слов для этого отсортированного слова". В 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

Ответ 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

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

Ответ 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())

Ответ 4

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

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

Ответ 5

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

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

Например

a # 1 = 1 b # 1 = 2 С# 1 = 4 a # 2 = 2 ^ 26 b # 2 = 2 ^ 27

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

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

n * 26 бит

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

Ответ 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);
}

Ответ 7

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

unsigned char letter_frequency[26];

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

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

Вот рубиновая функция для вычисления подписи данного слова и сохранения ее в хеш, в то же время отбрасывая дубликаты. Из Hash я позже построил таблицу 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

Ответ 8

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

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

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

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

Ответ 9

В 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 и возвращают это как совпадение.

Ответ 10

Я создам hasmap, основанный на образцовом слове, и остальные алфавиты, которые мне все равно.

Например, если слово "car" моя хэш-таблица будет выглядеть так: а, 0 б, MAX с, 1 д, MAX е, MAX ... .. г, 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 + " ");
                }
            }

Ответ 11

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

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

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

Пример: abc cba

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

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

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

Ответ 12

версия 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))

Ответ 13

Просто добавьте простое решение 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())