Как найти анаграмму в тексте

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

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

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

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

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

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

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

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

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

Задача

:

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

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

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

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

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

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

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

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

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

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

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

 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 секунд

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

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

Что такое анаграмма?

Анаграмма – это состояние, при котором одна строка или число переставляются таким образом; каждый символ измененной строки или числа должен быть частью другой строки или числа. Другими словами, строка называется анаграммой другой, если вторая является простой перестановкой первой строки. Например: Python и yphton являются анаграммами; Java и avaJ также являются анаграммами.

Давайте разберемся с описанием проблемы определения анаграммы:

• Получите строковые входные данные от пользователя и сохраните их в отдельных переменных.
• Используйте метод sort() для сортировки обеих строк в списки.
• Проверьте оба списка, образуют ли они анаграмму или нет.
• Распечатайте результат.
• Выход.

Программа –

 
def anagramCheck2(str1,str2): 
    # Convert string into lists 
    list1 = list(str1) 
    list2 = list(str2) 
    # Sort the list value 
    list1.sort() 
    list2.sort() 
 
    position = 0 
    matches = True 
 
    while position < len(str1) and matches: 
        if list1[position]==list2[position]: 
            position = position + 1 
        else: 
            matches = False 
 
    return matches 
 
print(anagramCheck2('python','ythonp')) 

Выход:

True 

Объяснение –

В приведенном выше коде мы объявили метод anagramCheck(), который принимает в качестве аргумента две строки. Эти строки преобразуются в список для сортировки. Затем мы определили переменную позиции и присвоили ей ноль. На каждой итерации цикла while длина строки сравнивается со значением позиции. Каждый элемент обоих списков сравнивал друг друга и увеличивал значение позиции на единицу. Как только значение позиции станет больше, чем длина строки, цикл будет завершен и вернет истину; в противном случае он вернет false.

Есть несколько методов и примеров, которые мы можем использовать для поиска анаграммы в Python. Эти методы приведены ниже.

1. Техника подсчета

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

Давайте разберем на примере.

 
from collections import Counter, defaultdict 
def checking_anagram(keywords): 
    agrms = defaultdict(list) 
    for i in keywords: 
        hist = tuple(Counter(i).items()) 
        agrms[hist].append(i) 
    return list(agrms.values()) 
keywords =("python","yphotn") 
print(checking_anagram(keywords)) 

Выход:

[['python'], ['yphotn']] 

Объяснение –

Мы импортировали модуль коллекции и его методы Count и defaultdict, чтобы проверить анаграмму строки в приведенном выше коде. Мы определили метод check_anagram() для подсчета и записи каждого символа с помощью функции счетчика. Каждый счет преобразуется в список и отслеживается. Этот процесс выполняется для всех символов в первой строке, кроме второй. Если количество обеих строк совпадает, это означает, что обе строки являются анаграммами.

2. Метод сортировки

В этом методе обе строки сортируются и проверяют, соответствуют ли оба значения друг другу. Давайте разберемся в следующем примере.

Пример –

 
def Anogram_check(str1, str2): 
    # Strings are sorted and check whether both are matching or not 
    if(sorted(str1)== sorted(str2)): 
        print("Both strings are an Anagram.") 
    else: 
        print("Both strings are not an Anagram.") 
        
string1 ="python" 
string2 ="ythopn" 
print( "String value1 : ", str1 ) 
print( "String value2 : ", str2 ) 
Anogram_check(string1, str2) 

Выход:

String value1 :  python 
String value2 :  ythopn 
Both strings are an Anagram. 

Объяснение –

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

3. Обратная проверка анаграммы

Мы можем применить эту технику следующим образом.

Пример –

 
words_list = ["cat", "tac", "Play", "ay"] 
anagrams = {} 
for w in words_list: 
    reverse_word=w[::-1] 
    if reverse_word in words_list: 
         anagrams[w] =(words_list.pop(words_list.index(reverse_word))) 
         print(anagrams) 

Выход:

{'cat': 'tac'} 

Объяснение –

В приведенном выше коде мы использовали этот метод для сравнения анаграмм среди перевернутой строки. Здесь мы сформировали две разные строки. Этот метод похож на палиндромы, где мы перевернули одну строку и проверили ее с другими строками. Если они совпадают, струны образуют анаграмму; если они не совпадают, они не определяются как анаграммы.

4. Методика проверки положения

В этом методе уровень позиции сравнивается с проверкой анаграммы. Мы можем добиться этого, сверяя позиционный символ первой строки с каждой позиционной символьной строкой в другой строке. Если первая строка совпадает с другой строкой, она объявляется анаграммой.

Пример –

 
def checking_anagram(str1,str2): 
    chk_var = True 
    if len(str1) != len(str2): 
        chk_var = False 
        list1 = list(str2) 
    pos_string1 = 0 
    while pos_string1 < len(str1) and chk_var: 
        pos_string2 = 0 
        found = False 
    while pos_string2 < len(list1) and not found: 
        if str1[pos_string1] == list1[pos_string2]: 
            found = True 
        else: 
            pos_string2 = pos_string2 + 1 
    if found: 
        list1[pos_string2] = None 
    else: 
        chk_var = False 
        pos_string1 = pos_string1 + 1 
    return chk_var 
 
 
str1 = "ythopn" 
str2 = "python" 
print("String value1 : " , str1) 
print("String value2 : " , str2) 
Boolean_out = checking_anagram('ythopn','python') 
if Boolean_out: 
    print( "Both words are Alogram " ) 
else: 
    print( "Both words are not Alogram " ) 

Выход:

String value1 :  ythopn 
String value2 :  python 

Объяснение:

В этом еще одна техника получения анаграммы двух строк. Здесь мы также использовали сравнение. Во вложенном цикле while мы передаем строку в эти циклы для процесса проверки.

Внешний цикл while используется для обработки одной из строк, а внутренний цикл – для другой строки. Символ одной строки сравнивается с другой строкой каждого символа, и этот процесс продолжается для каждой буквы в первой строке. Если все символы первой строки совпадают с другой строкой, то обе строки должны быть анаграммой. Этот метод – очень стабильный процесс, потому что он работает по алгоритму, точно оценивая строки.

# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
        "Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP",
         "Protijayi","Paikpara","dipSouta","Shyambazaar",
        "jayiProti", "North Calcutta", "Sovabazaar"]

#Method 1
A = [''.join(sorted(word)) for word in words]

dict ={}

for indexofsamewords,samewords in enumerate(A):
    dict.setdefault(samewords, []).append(indexofsamewords)
    
print(dict)
#{'AOOPR': [0, 2, 5, 9, 11], 'ABTU': [1, 3, 4], 'Sadioptu': [6, 14], ' KPaaehiklry': [7], 'Taeggllnouy': [8], 'Leov': [10], 'Paiijorty': [12, 16], 'Paaaikpr': [13], 'Saaaabhmryz': [15], ' CNaachlortttu': [17], 'Saaaaborvz': [18]}

for index in dict.values(): 
    print( [words[i] for i in index ] )
    

The Output :

['ROOPA', 'OOPAR', 'PAROO', 'AROOP', 'AOORP']
['TABU', 'BUTA', 'BUAT']
['Soudipta', 'dipSouta']
['Kheyali Park']
['Tollygaunge']
['Love']
['Protijayi', 'jayiProti']
['Paikpara']
['Shyambazaar']
['North Calcutta']
['Sovabazaar']