Привет, Хабр.

Для одного из моих проектов мне понадобилось сделать фильтр мата. Сегодня мы попытаемся сделать его за несколько минут. Ну что же, приступим.

Анализирование

Сперва я должен бы как-то разбивать текст на части, чтобы потом сравнивать его с нецензурной лексикой. Решение нашлось очень просто. Я составил список запрещенных слов и стал проходится циклом по введенному тексту, разбивая его на куски размером с каждое запрещенное слово.

#Фраза, которую будем проверять.
phrase = input("Введите фразу для проверки: ")

#Искомое слово. Пока что только одно.
words = ["банан"]

#Фрагменты, которые получатся после разбиения слова.
fragments = []
#Проходимся по всем словам.
for word in words:
    #Разбиваем слово на части, и проходимся по ним.
    for part in range(len(phrase)):
        #Вот сам наш фрагмент.
        fragment = phrase[part: part+len(word)]
        #Сохраняем его в наш список.
        fragments.append(fragment)

#Выводим получившиеся фрагменты.
print(fragments)

Запускаем наш файл и вводим фразу.

Введите фразу для проверки: Привет, я банан.
['Приве', 'ривет', 'ивет,', 'вет, ', 'ет, я', 'т, я ', ', я б', ' я ба', 'я бан', ' бана', 'банан', 'анан.', 'нан.', 'ан.', 'н.', '.']

Вот что у нас получилось. Смотрим на все фрагменты и видим среди них искомое слово «банан». Теперь нам осталось сравнить эти фрагменты с искомыми словами.

Сравнение

Для того, чтобы сравнивать фрагменты с искомыми словами, я решил просто использовать цикл.

#Проходимся по всем словам.
for word in words:
    #Проходимся по всем фрагментам.
    for fragment in fragments:
        #Сравниваем фрагмент и искомое слово
        if word == fragment:
            #Если они равны, выводим надпись о их нахождении.
            print("Найдено", word)

Смотрим.

Введите фразу для проверки: Привет, я банан.
['Приве', 'ривет', 'ивет,', 'вет, ', 'ет, я', 'т, я ', ', я б', ' я ба', 'я бан', ' бана', 'банан', 'анан.', 'нан.', 'ан.', 'н.', '.']
Найдено банан

Все, простейший фильтр нецензурной лексики готов!

Доработки

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

Так как русский человек очень изобретателен, то он может поменять некоторые буквы на другой язык. Например, «бaнaн». Здесь место обычной «а», я поставил английскую. И теперь наш фильтр не будет распознавать это слово.

Введите фразу для проверки: Привет, я бaнaн.
['Приве', 'ривет', 'ивет,', 'вет, ', 'ет, я', 'т, я ', ', я б', ' я бa', 'я бaн', ' бaнa', 'бaнaн', 'aнaн.', 'нaн.', 'aн.', 'н.', '.']

Фильтр не вывел ничего, а значит не нашел слово. Поэтому мы должны создать дополнительный фильтр, который будет переводить буквы английского алфавита и похожие символы в русский текст.

В интернете я нашел вот такой список, который чуточку доработал.

d =   {'а' : ['а', 'a', '@'],
  'б' : ['б', '6', 'b'],
  'в' : ['в', 'b', 'v'],
  'г' : ['г', 'r', 'g'],
  'д' : ['д', 'd', 'g'],
  'е' : ['е', 'e'],
  'ё' : ['ё', 'e'],
  'ж' : ['ж', 'zh', '*'],
  'з' : ['з', '3', 'z'],
  'и' : ['и', 'u', 'i'],
  'й' : ['й', 'u', 'i'],
  'к' : ['к', 'k', 'i{', '|{'],
  'л' : ['л', 'l', 'ji'],
  'м' : ['м', 'm'],
  'н' : ['н', 'h', 'n'],
  'о' : ['о', 'o', '0'],
  'п' : ['п', 'n', 'p'],
  'р' : ['р', 'r', 'p'],
  'с' : ['с', 'c', 's'],
  'т' : ['т', 'm', 't'],
  'у' : ['у', 'y', 'u'],
  'ф' : ['ф', 'f'],
  'х' : ['х', 'x', 'h' , '}{'],
  'ц' : ['ц', 'c', 'u,'],
  'ч' : ['ч', 'ch'],
  'ш' : ['ш', 'sh'],
  'щ' : ['щ', 'sch'],
  'ь' : ['ь', 'b'],
  'ы' : ['ы', 'bi'],
  'ъ' : ['ъ'],
  'э' : ['э', 'e'],
  'ю' : ['ю', 'io'],
  'я' : ['я', 'ya']
}

Перед фильтрацией мы должны перевести весь текст в нижний регистр и убрать все пробелы, так как кто-нибудь может ввести искомые слова вот так: «БАНАН» или «б а н а н».

phrase = phrase.lower().replace(" ", "")

Теперь мы должны как-то сравнить этот список с нашим текстом. Для этого я создал вот такую функцию.

#Проходимся по нашему словарю.
for key, value in d.items():
    #Проходимся по каждой букве в значении словаря. То есть по вот этим спискам ['а', 'a', '@'].
    for letter in value:
        #Проходимся по каждой букве в нашей фразе.
        for phr in phrase:
            #Если буква совпадает с буквой в нашем списке.
            if letter == phr:
                #Заменяем эту букву на ключ словаря.
                phrase = phrase.replace(phr, key)

Что у нас получилось теперь.

Введите фразу для проверки: Привет, я б@н@н.
['Приве', 'ривет', 'ивет,', 'вет, ', 'ет, я', 'т, я ', ', я б', ' я ба', 'я бан', ' бана', 'банан', 'анан.', 'нан.', 'ан.', 'н.', '.']
Найдено банан

То, что у нас не находилось раньше теперь легко распознаётся.

Расстояние Левенштейна

Я понял, что если хоть чуточку изменить слово, то его уже невозможно найти.

Введите фразу для проверки: Я люблю бонан.
['Я люб', ' любл', 'люблю', 'юблю ', 'блю б', 'лю бо', 'ю бон', ' бона', 'бонан', 'онан.', 'нан.', 'ан.', 'н.', '.']

Наши опасения подтвердились, но решения этой проблемы есть расстояние Левенштейна.

В интернете я нашел функцию этого алгоритма для python. Вот как она выглядит.

def distance(a, b): 
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n, m)) space
        a, b = b, a
        n, m = m, n

    current_row = range(n + 1)  # Keep current and previous row, not entire matrix
    for i in range(1, m + 1):
        previous_row, current_row = current_row, [i] + [0] * n
        for j in range(1, n + 1):
            add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
            if a[j - 1] != b[i - 1]:
                change += 1
            current_row[j] = min(add, delete, change)

    return current_row[n]

Теперь мы должны переписать функцию сравнения.

#Проходимся по всем словам.
for word in words:
    #Проходимся по всем фрагментам.
    for fragment in fragments:
        #Если отличие этого фрагмента меньше или равно 25% этого слова, то считаем, что они равны.
        if distance(fragment, word) <= len(word)*0.25:
            #Если они равны, выводим надпись о их нахождении.
            print("Найдено", word)

Что у нас получилось теперь.

Введите фразу для проверки: Я люблю бонан.
['Я люб', ' любл', 'люблю', 'юблю ', 'блю б', 'лю бо', 'ю бон', ' бона', 'бонан', 'онан.', 'нан.', 'ан.', 'н.', '.']
Найдено банан

Небольшие проблемы

Наверное вы уже догадались, что если в списке для фильтрации будет больше одного слова, то он будет некорректно работать. Поэтому я переписал это всё в один цикл.

#Проходимся по всем словам.
for word in words:
    #Разбиваем слово на части, и проходимся по ним.
    for part in range(len(phrase)):
        #Вот сам наш фрагмент.
        fragment = phrase[part: part+len(word)]
        #Если отличие этого фрагмента меньше или равно 25% этого слова, то считаем, что они равны.
        if distance(fragment, word) <= len(word)*0.25:
            #Если они равны, выводим надпись о их нахождении.
            print("Найдено", word, "\nПохоже на", fragment)

Все, наш фильтр полностью готов.

Код фильтра

import string

words = ["банан", "помидор"]

print("Фильтруемые слова:", words)

#Фраза, которую будем проверять.
phrase = input("Введите фразу для проверки: ").lower().replace(" ", "")

def distance(a, b): 
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n, m)) space
        a, b = b, a
        n, m = m, n

    current_row = range(n + 1)  # Keep current and previous row, not entire matrix
    for i in range(1, m + 1):
        previous_row, current_row = current_row, [i] + [0] * n
        for j in range(1, n + 1):
            add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
            if a[j - 1] != b[i - 1]:
                change += 1
            current_row[j] = min(add, delete, change)

    return current_row[n]

d =   {'а' : ['а', 'a', '@'],
  'б' : ['б', '6', 'b'],
  'в' : ['в', 'b', 'v'],
  'г' : ['г', 'r', 'g'],
  'д' : ['д', 'd'],
  'е' : ['е', 'e'],
  'ё' : ['ё', 'e'],
  'ж' : ['ж', 'zh', '*'],
  'з' : ['з', '3', 'z'],
  'и' : ['и', 'u', 'i'],
  'й' : ['й', 'u', 'i'],
  'к' : ['к', 'k', 'i{', '|{'],
  'л' : ['л', 'l', 'ji'],
  'м' : ['м', 'm'],
  'н' : ['н', 'h', 'n'],
  'о' : ['о', 'o', '0'],
  'п' : ['п', 'n', 'p'],
  'р' : ['р', 'r', 'p'],
  'с' : ['с', 'c', 's'],
  'т' : ['т', 'm', 't'],
  'у' : ['у', 'y', 'u'],
  'ф' : ['ф', 'f'],
  'х' : ['х', 'x', 'h' , '}{'],
  'ц' : ['ц', 'c', 'u,'],
  'ч' : ['ч', 'ch'],
  'ш' : ['ш', 'sh'],
  'щ' : ['щ', 'sch'],
  'ь' : ['ь', 'b'],
  'ы' : ['ы', 'bi'],
  'ъ' : ['ъ'],
  'э' : ['э', 'e'],
  'ю' : ['ю', 'io'],
  'я' : ['я', 'ya']
}

for key, value in d.items():
    #Проходимся по каждой букве в значении словаря. То есть по вот этим спискам ['а', 'a', '@'].
    for letter in value:
        #Проходимся по каждой букве в нашей фразе.
        for phr in phrase:
            #Если буква совпадает с буквой в нашем списке.
            if letter == phr:
                #Заменяем эту букву на ключ словаря.
                phrase = phrase.replace(phr, key)

#Проходимся по всем словам.
for word in words:
    #Разбиваем слово на части, и проходимся по ним.
    for part in range(len(phrase)):
        #Вот сам наш фрагмент.
        fragment = phrase[part: part+len(word)]
        #Если отличие этого фрагмента меньше или равно 25% этого слова, то считаем, что они равны.
        if distance(fragment, word) <= len(word)*0.25:
            #Если они равны, выводим надпись о их нахождении.
            print("Найдено", word, "\nПохоже на", fragment)