Поиск анаграмм и сабанаграмм во всех словах языка

    Решение задач с анаграммами натолкнуло на мысль:
    Сколько останется слов, если удалить все анаграммы и сабанграммы из словаря русского языка

    В найденном словаре больше 1,5 млн слов в различных формах

    Можно сравнить каждое слово с каждым, но для 1,5 млн записей это долго и неоптимально.
    В мире с бесконечной памятью можно сгенерировать подстроки всех перестановок каждого слова и проверить наш словарь на них

    Но есть ли решение получше?

    Начнем с терминологии:

    Анаграмма — слово, получаемое перестановкой букв
    Пример: ракета и карета

    Сабанаграмма — слово, которое можно составить из букв другого слова
    Пример: арка — сабанаграмма слова ракета

    Задача:

    Допустим наш словарь состоит из пяти хитрых слов:

    ракета, карета, арка, кот, мокрота

    Добавляем словарь в префиксное дерево (Trie)
    Каждый узел дерева содержит пару: буква + ее количество в слове
    Узлы отсортированы по алфавиту и частоте буквы в слове



    Алгоритм (в упрощенной форме):

    Берем слово, н.р. кот:

    Ищем узлы, начинающиеся на минимальную букву слова («к»)

    (На рисунке такие узлы отмечены сиреневым)

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

    В слове мокрота ниже узла K-1 есть O-2 и Т-1, что для нашего слова кот достаточно

    Преимущество такой структуры данных в том, что мы можем быстро выходить из поддерева, если буква узла > чем искомая буква

    Проверив наш словарь, мы выяснили, что только мокрота не является анаграммой или сабанаграммой другого слова

    Код на Java
     public boolean isAnagramOrSubAnagram(Word word) {
            Character minCharacter = word.getMinCharacter();
    
            Stack<TrieNode> stack = new Stack<>();
            stack.add(root);
    
            while (!stack.isEmpty()) {
                TrieNode node = stack.pop();
    
                for (Entry<TrieKey, TrieNode> entry : node.getChildren().entrySet()) {
                    char character = entry.getKey().getCharacter();
                    if (character < minCharacter) {
                        stack.add(entry.getValue());
                    } else if (character > minCharacter) {
                        break;
                    } else if (entry.getKey().getCount() >= word.getCharacterCount(minCharacter)) {
                        if (doesMinWordCharacterNodeContainAnagram(entry, word)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    
    


    Полная версия кода с двумя словарями и тестами

    P.S.

    Для русского словаря от 1.5 млн. осталось 242399 слов за 13 минут
    Для английского словаря от 416 тыс. осталось 49251 за 45 секунд

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

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 6

      +10
      Тут trie неестественно смотрится. Для [саб]анаграмм порядок букв в слове не важен, поэтому каждое «слово» это просто мешок букв. А trie для строк/слов. В данной задаче каждое слово можно представить как 33-мерный вектор, каждая координата — сколько раз встречается соответствующая буква. Например, «карета» будет <2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 >. Слово является [саб]анаграммой другого слова, если у него значения по всем координатам не больше чем у другого слова. Или, можно сказать, если каждое слово представить кубом <0,0,0...,0>—<a1,a2,...,a33>, то слово будет [саб]анаграммой другого слова, когда его куб полностью лежит внутри другого куба.

      То есть логично хранить слова в какой-нибудь структуре данных для многомерных точек. Например, в R-tree.

      Чтобы не заморачиваться с операцией удаления, вначале надо отсорировать словарь по длине слова ­— от длинных к коротким. После этого для каждого слова — проверить есть ли оно в R-tree, если есть, то выбросить, если нет, то вставить и вывести как не-анаграмму.
        +3
        Изящное решение. Я аплодирую.
          +1

          Прямо как на собеседовании в гугл.
          Супер!

          –3
          каждое «слово» это просто мешок букв.

          Я бы слегка продвинул аллегорию: каждая буква — это мешок с монетами, на одной стороне монеты — Id слова в словаре, на другой стороне — количество повторений буквы в слове. Мешок отсортирован по количеству повторений. 33 букв в алфавите — 33 мешка. Каждый мешок обслуживается своим ядром процессора. Дальше — каждый в соответствии со своим воображением.
            0
            Прикольно, за что столько минусов? Просто предложил 33 таблицы по количеству букв в алфавите. Запись в такой таблице — это Id слова и количество повторений этой буквы в этом слове. Типа первый ход в шахматной задаче. Наверно кто-то ночей не спит, пытается продвинуться дальше, иначе бы просто прошел мимо. Чего притормаживать, — ни политики, ни секса, ни криминала, — не понял что-то, — просто двигай дальше.
            0
            Для быстрого определения анаграммы или субанаграммы я использовал для слов построенные индексы длиной uint32 (unsigned int) — если буква в принципе встречается, то её бит установлен, если нет — не установлен (Е=Ё). Для анаграммных слов этот индекс будет совпадать. Для субанаграммных — один индекс включается в другой. Требуется дополнительная проверка слов, но индекс позволяет очень сильно отсеять неподходящие слова.
            https://qna.habr.com/q/712389#answer_1528267

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

            Самое читаемое