Вопрос по hash, anagram, data-structures – получить список анаграмм из словаря

6

По сути, анаграммы подобны перестановке строк. Например,stack ,sackt ,stakc все анаграммыstack (мысли выше слова не имеют смысла). В любом случае вы могли бы понять, что я имел в виду.

Теперь я хочу списокanagrams дали миллион слов или просто сказали из словаря.

Мой основной вопросFind total number of unique anagrams in a dictionary?

Сортировка и сравнение не будет работать, так как сложность времени довольно плохая.

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

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

Благодарю.

да @ Алекс. Я просто хочу, сколько там разных анаграмм? vijay
вопрос не до конца понятен. Можете ли вы перефразировать цель? Nicholas DiPiazza
@NicholasDiPiazza, надеюсь, моя цель вам ясна. vijay
Вы имеете в виду: у меня есть словарь из миллиона слов, я хочу определить все наборы слов в словаре, которые являются анаграммами друг друга? Например. Если бы словарь содержал: [tap, pat, pot, top], вы бы хотели видеть [[tap, pat], [pot, top]]? Alex Wilson
Решением здесь является сортировка, а ее сложность линейна, если принять некоторую постоянную верхнюю границу длины слова. Вы просто должны отсортировать правильную вещь; персонажи, а не слова. Fred Foo

Ваш Ответ

5   ответов
2

их слов) отсортированный счетчик числа вхождений каждой буквы. Так что для "анаграммы" вы бы сгенерировали [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r', 1)].

В качестве альтернативы вы могли бы получить неточную группировку, сгенерировав битовую маску из своего слова, где для битов 0-25 каждый бит представлял наличие или отсутствие этой буквы (бит 0, представляющий от "а" до бита 25, представляющего "z"). Но тогда вам придется выполнить немного больше обработки, чтобы разделить каждую хешированную группу дальше, чтобы различить, например, & Quot; с & Quot; от "тоже".

Поможет ли одна из этих идей? Любой конкретный язык реализации (я мог бы сделать C ++, Python или Scala)?

Edit: added some example Scala code and output:

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

Используя большой список английских слов отсюда:http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

Я запускаю на них этот код Scala (занимает около 5 секунд, используя Scala 2.9 в режиме сценария, включая время на компиляцию, со словарем из примерно 40000 слов. Не самый эффективный код, но первое, что пришло в голову).

// Hashing function to go from a word to a sorted list of letter counts
def toHash(b:String) = b.groupBy(x=>x).map(v => (v._1, v._2.size) ).toList.sortWith(_._1 < _._1)


// Read all words from file, one word per line
val lines = scala.io.Source.fromFile("2of12.txt").getLines

// Go from list of words to list of (hashed word, word)
val hashed = lines.map( l => (toHash(l), l) ).toList

// Group all the words by hash (hence group all anagrams together)
val grouped = hashed.groupBy( x => x._1 ).map( els => (els._1, els._2.map(_._2)) )

// Sort the resultant anagram sets so the largest come first
val sorted = grouped.toList.sortWith( _._2.size > _._2.size )

for ( set <- sorted.slice(0, 10) )
{
    println( set._2 )
}

Это выдает первые 10 наборов анаграмм (наборов с наибольшим количеством членов первым):

List(caret, cater, crate, react, trace)
List(reins, resin, rinse, risen, siren)
List(luster, result, rustle, sutler, ulster)
List(astir, sitar, stair, stria, tarsi)
List(latrine, ratline, reliant, retinal)
List(caper, crape, pacer, recap)
List(merit, miter, remit, timer)
List(notes, onset, steno, stone)
List(lair, liar, lira, rail)
List(drawer, redraw, reward, warder)

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

Edit 2: You can replace the hash function with a simple sort on the chars of each word (as suggested by JAB) and get the same result with clearer/faster code:

def toHash(b:String) = b.toList.sortWith(_<_)
Не могли бы вы помочь мне объяснить алгоритм. Это было бы очень полезно. vijay
Кажется, круто. Псевдокод будет здорово. Спасибо vijay
Я не знаю Scala. Всегда спасибо за ваши усилия. vijay
23

ь простые числа. Так что, если "a"; " - & GT; 2 и 'b' - & GT; 3, то

'ab' -> 6 'ba' -> 6 'bab' -> 18 'abba' -> 36 'baba' -> 36

Чтобы минимизировать вероятность переполнения, наименьшие простые числа могут быть назначены более частым буквам (e, t, i, a, n). Примечание: 26-е простое число - 101.

ОБНОВИТЬ: реализацию можно найти здесь

Действительно блестящий!
Да. Я понял. До сих пор я нахожу твой подход клевым. vijay
Ну, что ж, спасибо! Обратите внимание, что (как только вы столкнетесь с коллизиями), он будет работать с не простыми (random) номера тоже. Это похоже на хеширование Zobrist. Но с простыми числами этоlooks очиститель.
Вам все еще приходится иметь дело с переполнением, которое может привести к "столкновениям". Вероятно, сохраняя буквенные частотные гистограммы с каждой записью.
кажется круто. спасибо. vijay
1

а затем XOR результат по длине ввода, вы получите одно и то же значение независимо от порядка слова, а это означает, что все анаграммы будут производить один и тот же хэш. (XOR по длине препятствует тому, чтобы 'boss' и 'bo' возвращали одно и то же значение, потому что хэш 's' против самого себя всегда равен 0.)

Пример:

int AnagramHash(string input)
{
    int output = 0;

    foreach(char c in input)
        output ^= c.GetHashCode();

    return output ^ input.Length;
}

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

РЕДАКТИРОВАТЬ: Также, как примечание, XOR - самая простая операция, выполняемая ALU, поэтому, если вы в конечном итоге будете использовать ее, вы сможете довольно быстро сгенерировать ваши хэши.

Как вы получаете уникальные хэш-коды? vijay
Любая проблема, если я использую простые числа для кодирования каждого из символов?
& quot; Вам все равно придется искать все слова с тем же AnagramHash. & quot; Нет, если вы поместите слова в списки / и т.д. которые хранятся в местах в словаре, указанномAnagramHash.
В C #GetHashCode() это метод на всех классах. По сути, он генерирует уникальное целочисленное значение для любого объекта. (Объекты с одним и тем же значением выдают одно и то же целое число.) Для другого языка вы можете просто использовать значение байта каждого символа в качестве хеш-кода, поскольку они все равно будут уникальными для каждого значения.
0

t work as it's time complexity is pretty bad.

Обменивая временную сложность на дополнительную память, просто сохраняйте количество букв в слове в 26-char (или эквивалент на любом языке, который вы используете, и предполагая, что вы используете латинский алфавит и только буквенные символы) массив и хэшируйте массив. Вы застряли с O (n) временем относительно длины слова, но большинство английских слов на самом деле не такие длинные.

напримерstack, sackt, а такжеstakc будет иметь массив с местами дляs, t, a, c, k == 1, а все остальные равны 0.

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

Это так, но вы сказали, что не хотите сортировать, поэтому я дал вам то, что не связано с сортировкой.
В основном, я обеспокоен сложностью времени. И взгляну на другой ответ. Я думаю, что он позаботится об обеих сложностях. Спасибо vijay
Ну, я обновил свой ответ с дополнительной возможностью.
Алекс не сортирует символы. Он делает отсортированное количество символов в слове, что довольно круто. В любом случае, спасибо за вашу помощь. vijay
Спасибо. Извините, я где-то потерялся: P vijay
0

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

Вопрос похож на «найти все анаграммы слова в файле»

Посмотреть алгоритм и код здесьhttp://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html

Похожие вопросы