Получить список анаграмм из словаря
По сути, анаграммы подобны перестановке строк. Например, stack,sackt,stakc все анаграммы stack (мысли выше слова не имеют смысла). В любом случае вы могли бы понять, что я имел в виду.
Теперь я хочу список anagrams дали миллион слов или просто сказали из словаря.
Мой основной вопрос Find total number of unique anagrams in a dictionary?
Сортировка и сравнение не будут работать, поскольку сложность времени довольно плохая.
Я думал об использовании хеш-таблицы, строка в качестве ключа.
Но проблема в том, какой должна быть хеш-функция? Было бы полезно, если бы предоставили какой-нибудь псевдокод. Некоторые другие подходы лучше упомянутых подходов также будут полезны.
Благодарю.
5 ответов
Очевидное решение состоит в том, чтобы сопоставить каждый символ простому числу и умножить простые числа. Так что если "а" -> 2 и "б" -> 3, то
- 'ab' -> 6
- 'ba' -> 6
- 'bab' -> 18
- 'abba' -> 36
- 'баба' -> 36
Чтобы минимизировать вероятность переполнения, наименьшие простые числа могут быть назначены более частым буквам (e,t,i,a,n). Примечание: 26-е простое число - 101.
ОБНОВЛЕНИЕ: реализация может быть найдена здесь
Одной из возможных хеш-функций может быть (при условии только английских слов) отсортированный счетчик количества вхождений каждой буквы. Таким образом, для "анаграммы" вы должны сгенерировать [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r',1)].
В качестве альтернативы вы можете получить неточную группировку, сгенерировав битовую маску из своего слова, где для битов 0-25 каждый бит представляет наличие или отсутствие этой буквы (биты от 0 до 25, представляющие "z"). Но тогда вам придется сделать немного больше обработки, чтобы разделить каждую хешированную группу дальше, чтобы отличить, например, "до" от "слишком".
Помогает ли какая-либо из этих идей? Любой конкретный язык реализации (я мог бы сделать C++, Python или Scala)?
Редактировать: добавлен пример кода Scala и вывод:
ОК: Сейчас я нахожусь в режиме 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)
Обратите внимание, что здесь используется первое предложение (список из числа букв), а не более сложный метод битовой маски.
Редактировать 2: Вы можете заменить хэш-функцию простой сортировкой по символам каждого слова (как предложено JAB) и получить тот же результат с более ясным / быстрым кодом:
def toHash(b:String) = b.toList.sortWith(_<_)
Если вы XOR значения хеш-кода каждого символа, а затем 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, поэтому, если вы в конечном итоге используете его, вы должны быть в состоянии генерировать ваши хэши довольно быстро.
Используйте хэш-карту со строкой в качестве ключа и списком (строкой) в качестве значения, где список строк содержит все анаграммы ключевой строки.
Вопрос похож на "найти все анаграммы слова в файле"
Посмотреть алгоритм и код здесь http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html
Сортировка и сравнение не будут работать, поскольку сложность времени довольно плохая.
Обменивая временную сложность на дополнительную память, просто сохраняйте количество букв в слове в 26-char (или эквивалент на любом языке, который вы используете, и предполагая, что вы используете латинский алфавит и только буквенные символы) массив и хэшируйте массив. Вы застряли с O(N) времени относительно длины слова, но большинство английских слов на самом деле не так долго.
например stack, sackt, а также stakc будет иметь массив с местами для s, t, a, c, k == 1, а все остальные равны 0.
Исходя из вашего комментария, который подразумевает, что вы действительно в порядке с сортировкой символов слова, если вы сами не сортируете слова, вы можете сделать что-то даже более простое, чем ответ Алекса, и просто отсортировать символы в строках и хэше слова результаты, достижения. (Ларсман сказал это первым, но не опубликовал это как ответ, так что...)