Как элегантно вычислить подпись анаграммы слова в рубине?

Question

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

Идея заключается в том, чтобы отсортировать буквы в слове, а также выполнить кодирование повторяющихся букв по длине. Так, например, «Миссисипи» сначала становится «iiiimppssss», а затем может быть сокращено путем кодирования как «4impp4s».

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

edit: чтобы уточнить, производительность вычисления подписи не имеет большого значения для моего приложения. Я хочу вычислить подпись, чтобы я мог сохранить ее с каждым словом в большой базе данных слов (450 тыс. Слов), а затем запросить слова, которые имеют одинаковую подпись (то есть все анаграммы данного слова, которые являются фактическими английскими словами). ). Отсюда акцент на пространстве. «Элегантная» часть просто для удовлетворения моего любопытства.

Answer 1

Самый быстрый способ создать отсортированный список букв - это:

"mississippi".unpack("c*").sort.pack("c*")

Это немного быстрее, чем split ('') и join (). Для сравнения также лучше упаковать массив обратно в строку, так что вам не нужно сравнивать массивы.

Answer 2

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

s = "mississippi"
s.split('').sort.join.gsub(/(.)\1{2,}/) { |s| s.length.to_s + s[0,1] } 

Конечно, вам нужно убедиться, что слово строчное, не содержит цифр и т. Д.

По запросу я постараюсь объяснить код. Пожалуйста, прости меня, если я не понимаю всю терминологию Ruby или reg ex, но здесь все.

Я думаю, что разделить / отсортировать / объединить довольно просто. Интересная часть для меня начинается с звонка в gsub. Это заменит подстроку, которая соответствует регулярному выражению, возвращаемым значением из блока, следующего за ним. Reg ex находит любого персонажа и создает обратную ссылку. Это часть "(.)". Затем мы продолжаем процесс сопоставления, используя обратную ссылку "\ 1", которая оценивает любой символ, найденный в первой части совпадения. Мы хотим, чтобы этот символ был найден как минимум еще два раза для общего минимального числа вхождений три. Это делается с помощью квантификатора "{2,}".

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

Я прошу прощения, если это сбивает с толку. Как это часто бывает, мне проще визуализировать решение, чем четко его объяснить.

Answer 3

Я не вижу элегантного решения. Вы можете использовать сообщение split, чтобы получить символы в массив, но затем, после того как вы отсортируете список, я не вижу симпатичного примитива линейного времени для возврата к строке. Я удивлен.

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

--- Ирма Веп

---

РЕДАКТИРОВАТЬ : другой плакат нашел join, который я пропустил. Ницца.