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

Присвойте уникальный простой номер a-z

букв, Выполняют итерации Вашего массива слова, создавая продукт начал на основе букв в каждом слове.
Хранилище, что продукт в Вашем списке слов, с соответствующим словом.

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

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

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

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

, Например

№ 1 = 1 b № 1 = 2 c № 1 = 4 № 2 = 2^26 b № 2 = 2 ^ 27

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

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

n * 26 битов

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

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

Сумма букв никогда не будет работать, потому что Вы не можете действительно сделать 'ac' и 'bb' отличающимся.

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

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

Присваивают началам 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

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

Я реализовал это прежде с простым массивом количеств буквы, например:

unsigned char letter_frequency[26];

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

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

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

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

Я сгенерирую hasmap на основе слова-образца и остальных алфавитов, мне все равно.

Например, если слово "машина" моя хеш-таблица будет иметь следующий вид: a, 0 b, MAX c, 1 { {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 + " ");
                }
            }