Разбор: подсказки по началу слова и опечатки

Если ты умеешь находить слова по префиксу двоичным поиском и знаешь, чем генерация правок лучше расстояния до каждого слова, листай до «Теперь сам».

Как думаешь, что здесь дорого

В словаре магазина миллион названий. Человек набирает «kave» - нужно показать подходящие названия быстрее, чем он наберёт следующую букву, а если он набрал «kavre» вместо «kaver», всё равно понять, что он имел в виду. Что здесь дорого, а что дёшево?

Ответь себе до чтения. Дорого - всё, что для каждого запроса смотрит на каждое слово словаря: миллион проверок на каждое нажатие клавиши. Дёшево - то, что зависит от длины запроса, а не от словаря.

На что это похоже

Бумажный словарь. Чтобы найти все слова на «кав», его не читают подряд - открывают посередине, потом посередине половины, и через десяток шагов палец стоит на первом слове с «кав». Все остальные идут следом. С опечаткой поступают так же, как человек со словарём: «кавре - нет такого; может, кавер?» - перебирают похожие написания запроса, а не сравнивают его со всеми словами.

Механизм: от просьбы к модели

Вход - словарь (меняется редко) и поток запросов (на каждое нажатие). Вид ответа - все слова с этим началом, точнее первые несколько; для опечатки - слова на расстоянии одной правки. Размер - 10⁶ слов, ответ за миллисекунды.

Отсюда первое решение по устройству: словарь обрабатывается один раз - сортируется, складывается в множество, - а запрос стоит в основном по своей длине. Префиксу - длина, умноженная на логарифм размера словаря: от словаря цена растёт, но медленно; правкам - около 53n строк по n символов, то есть n², при любом словаре. К этому прибавляется выдача: сколько слов подошло, столько и отдать, если не ограничить число подсказок.

Префикс. В отсортированном списке слова, начинающиеся на p, идут подряд: от первого слова ≥ p до первого слова ≥ p с приписанным символом, который больше любой буквы. Две границы - два двоичных поиска (раздел 6).

Опечатка. Расстояние редактирования (раздел 15) - наименьшее число вставок, удалений и замен символа. «Одна опечатка» - расстояние 1. Можно считать его до каждого слова словаря, а можно наоборот - сгенерировать все строки на расстоянии 1 от запроса и проверить каждую в множестве. В генератор ниже добавлена ещё и перестановка соседних букв, которой в этом определении нет: так он считает опечатку чуть шире - к чему это ведёт, покажет сверка двух способов в разборе. Их немного: для запроса длины n над алфавитом из 26 букв это n удалений, до n − 1 перестановок соседних, 25n замен и 26(n + 1) вставок - не больше 53n + 25 строк, сколько бы слов ни было в словаре. Замену на ту же букву и перестановку двух одинаковых соседей пропускают: они вернули бы сам запрос, а он не опечатка.

Правило

Подготовь словарь один раз - отсортируй, сложи в множество, - чтобы запрос стоил по длине запроса, а не по размеру словаря. Префикс - два двоичных поиска в отсортированном списке. Одна опечатка - перебор правок запроса с проверкой в множестве. И запиши в спецификацию, какие правки считаются опечаткой.

Разбор: подсказки по префиксу двоичным поиском

Словарь из 400 придуманных слов, три запроса. Сверяем с перебором всех слов.

import random

random.seed(3)
slogi = ["ka", "ro", "mi", "sta", "lo", "ver", "pa", "ne", "tu", "dri"]
slova = set()
while len(slova) < 400:
    w = ""
    for i in range(random.randint(2, 4)):
        w = w + slogi[random.randint(0, 9)]
    slova.add(w)
slovar = sorted(slova)

sravnenij = [0]

def pervyj_ne_menshe(a, x):
    # двоичный поиск: первый номер, где a[i] >= x
    lo = 0
    hi = len(a)
    while lo < hi:
        sravnenij[0] = sravnenij[0] + 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def podskazki(prefiks):
    # все слова с префиксом идут в отсортированном словаре подряд:
    # от первого >= prefiks до первого >= prefiks + "~"; "~" больше
    # строчных латинских букв, а других в словаре нет
    l = pervyj_ne_menshe(slovar, prefiks)
    r = pervyj_ne_menshe(slovar, prefiks + "~")
    return slovar[l:r]

def perebor(prefiks):
    out = []
    for w in slovar:
        sravnenij[0] = sravnenij[0] + 1
        if w.startswith(prefiks):
            out.append(w)
    return out

for p in ["kaver", "dri", "stalo"]:
    sravnenij[0] = 0
    a = podskazki(p)
    s1 = sravnenij[0]
    sravnenij[0] = 0
    b = perebor(p)
    print(p, "-> найдено", len(a), a[:3], "| совпало:", a == b)
    print("   сравнений: двоичным поиском", s1,
          "перебором", sravnenij[0])

kaver -> найдено 5 ['kaver', 'kaverlone', 'kaverne'] | совпало: True
   сравнений: двоичным поиском 18 перебором 400
dri -> найдено 34 ['dridri', 'dridritu', 'dridriver'] | совпало: True
   сравнений: двоичным поиском 18 перебором 400
stalo -> найдено 1 ['staloka'] | совпало: True
   сравнений: двоичным поиском 17 перебором 400

Двоичный поиск делает около 2 log₂ 400 ≈ 17 сравнений на любой запрос, перебор - 400, и на миллионе слов это 40 против миллиона. Ответ выдаётся срезом списка: если нужны только первые десять подсказок, берут slovar[l:min(r, l + 10)] - без min срез прихватил бы слова с чужим началом, когда подходящих меньше десяти. С таким ограничением и длина ответа не зависит от словаря; весь срез slovar[l:r] растёт вместе с числом подходящих слов. Символ ~ после префикса - приём для верхней границы: он больше любой строчной латинской буквы, поэтому p + "~" больше всех слов на p - пока словарь латинский, как здесь. Кириллица и буквы с диакритикой больше ~, и для них приём ломается: верхней границей берут префикс с последним символом, увеличенным на единицу (p[:-1] + chr(ord(p[-1]) + 1)), - строки на p меньше её при любом алфавите. Пустой префикс - отдельный край: ему подходит весь словарь, и границы не нужны вовсе.

Разбор: правки запроса против расстояния до каждого слова

Теперь опечатки. Первый путь - сгенерировать правки запроса, второй - посчитать расстояние редактирования до каждого слова подходящей длины.

import random

random.seed(3)
slogi = ["ka", "ro", "mi", "sta", "lo", "ver", "pa", "ne", "tu", "dri"]
slova = set()
while len(slova) < 400:
    w = ""
    for i in range(random.randint(2, 4)):
        w = w + slogi[random.randint(0, 9)]
    slova.add(w)
bukvy = "abcdefghijklmnopqrstuvwxyz"
rabota = [0]

def pravki(w):
    # все строки на расстоянии одной правки: удалить, переставить
    # соседние, заменить, вставить букву
    out = []
    for i in range(len(w)):
        out.append(w[:i] + w[i + 1:])
    for i in range(len(w) - 1):
        if w[i] != w[i + 1]:       # одинаковые соседи - сам запрос
            out.append(w[:i] + w[i + 1] + w[i] + w[i + 2:])
    for i in range(len(w)):
        for b in bukvy:
            if b != w[i]:          # замена на ту же букву - сам запрос
                out.append(w[:i] + b + w[i + 1:])
    for i in range(len(w) + 1):
        for b in bukvy:
            out.append(w[:i] + b + w[i:])
    rabota[0] = rabota[0] + len(out)
    return out

def rasstoyanie(a, b):
    # расстояние редактирования (раздел 15), строка таблицы за строкой
    prosh = []
    for j in range(len(b) + 1):
        prosh.append(j)
    for i in range(1, len(a) + 1):
        tek = [i]
        for j in range(1, len(b) + 1):
            rabota[0] = rabota[0] + 1
            cena = 0
            if a[i - 1] != b[j - 1]:
                cena = 1
            tek.append(min(prosh[j] + 1, tek[j - 1] + 1,
                           prosh[j - 1] + cena))
        prosh = tek
    return prosh[len(b)]

po_alfavitu = sorted(slova)          # подготовка словаря - один раз
for zapros in ["kavre", "stalok"]:
    rabota[0] = 0
    najdeno = []
    for p in pravki(zapros):
        if p in slova and p not in najdeno:
            najdeno.append(p)
    r1 = rabota[0]
    rabota[0] = 0
    blizkie = []
    for w in po_alfavitu:
        if abs(len(w) - len(zapros)) <= 1:
            if rasstoyanie(zapros, w) <= 1:
                blizkie.append(w)
    print(zapros, "->", sorted(najdeno), "| проверок правками:", r1)
    print("   ", blizkie, "| клеток таблицы:", rabota[0])

kavre -> ['kaver'] | проверок правками: 290
    [] | клеток таблицы: 3430
stalok -> ['staloka'] | проверок правками: 343
    ['staloka'] | клеток таблицы: 6342

По работе всё ожидаемо: 290 и 343 проверки в множестве (53n + 25 при n = 5 и 6) против тысяч клеток таблиц - и на миллионе слов правок будет столько же, а клеток в тысячи раз больше.

Но на «kavre» ответы разошлись: правки нашли «kaver», расстояние редактирования - ничего. Это не ошибка программы, а два разных определения опечатки. В генерации правок есть перестановка соседних букв, kavre → kaver - одна правка. Программа считает расстояние Левенштейна из раздела 15: оно знает только вставку, удаление и замену, и для него перестановка стоит две замены. В том же разделе упоминался вариант с транспозицией - расстояние Дамерау-Левенштейна, и по нему здесь тоже одна правка. Какое нужно - решает спецификация: люди чаще всего путают именно соседние буквы, поэтому для поиска обычно берут второе. Сверка двух решений нашла вопрос, которого не было в просьбе, - ровно как в уроке о маленьком примере.

Что ломается без этого

Подсказки тормозят на большом словаре. Перебор всех слов на каждое нажатие - миллион проверок, десятки миллисекунд, и подсказка опаздывает за пальцами.

«Почему не находит?» Перестановка букв - самая частая опечатка, а выбранное расстояние её не считает одной правкой.

Поиск правок для длинных запросов и двух опечаток. Правок на расстоянии 2 - уже порядка (53n)²: при n = 8 это сотни тысяч кандидатов; для таких случаев строят специальные индексы, а не перебирают.

Зачем это в работе

Поиск по каталогу, автодополнение команд в терминале, подсказка адреса, проверка орфографии - всё это «подготовить словарь один раз, отвечать по длине запроса». Отсортированный список с двоичным поиском - самый простой индекс по префиксу; когда словарь часто меняется или нужна подсказка по середине слова, приходят бор и суффиксный массив из раздела 17.

Теперь сам

1. Сколько кандидатов сгенерирует перебор правок (с перестановками) для запроса из 8 букв латиницы?
2. В отсортированном словаре 10⁶ слов. Сколько сравнений нужно, чтобы найти все слова с данным префиксом?
3. Какое расстояние Левенштейна и какое Дамерау-Левенштейна между «abcd» и «acbd»?