Все вхождения: выходные ссылки и цена ответа

Если ты расставишь выходные ссылки для a, ba, aba, объяснишь, почему нельзя идти по суффиксным ссылкам на каждом символе, и скажешь, как посчитать вхождения без их перечисления, - листай до «Теперь сам».

Как думаешь, где стоял поиск, когда кончилось слово

В прошлом уроке поиск по тексту rakursa с образцами ak, rak, kurs, rakurs нашёл rak и rakurs. Слова ak и kurs в тексте есть, но найдены не были.

Прежде чем читать дальше, вспомни трассу и скажи: в каком узле бора стоял поиск в тот момент, когда в тексте кончилось слово ak? Заходил ли он вообще в узел ak? И как, стоя в другом узле, узнать, что ak тоже только что кончилось?

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

Представь матрёшку. Ты держишь в руках большую - и знаешь, что внутри неё может быть меньшая, в той - ещё меньшая. Чтобы перечислить всё, что у тебя в руках, одной большой мало: надо назвать и вложенные.

Суффиксная ссылка - это «открой и посмотри, что внутри». Но большинство оболочек пустые: внутри узла raku лежит ku, внутри него - ничего интересного, ни одно слово там не кончается. Открывать каждую оболочку ради того, чтобы убедиться в этом, - лишняя работа. Выходная ссылка - записка, приклеенная заранее: «ближайшая матрёшка с подарком внутри - вот эта». Если записки нет, внутри можно не искать.

Механизм: цепочка ссылок и ближайший помеченный узел

Поиск стоит в узле rak. Его строка - последние три символа текста. Но последние ДВА символа - ak - тоже образец. Узел ak поиск не посещал: он шёл по ветке r-a-k. Связывает их суффиксная ссылка: rak → ak.

Общий факт: в позиции текста кончаются ровно те образцы, чьи узлы лежат на цепочке суффиксных ссылок от текущего узла до корня (включая сам текущий узел). Цепочка перебирает все концы строки текущего узла, которые есть в боре, от длинного к короткому.

цепочка от rak:       rak* → ak* → k → корень            кончаются rak и ak
цепочка от rakurs:    rakurs* → kurs* → корень           кончаются rakurs и kurs
цепочка от rakur:     rakur → kur → r → корень           ничего не кончается

Третья строка показывает цену наивного решения: три шага по цепочке, и все впустую.

Выходная ссылка узла ведёт в ближайший ПОМЕЧЕННЫЙ узел на его цепочке суффиксных ссылок, не считая самого узла. Если помеченных нет, выходной ссылки нет.

узел       суффиксная ссылка     выходная ссылка
rak        ak                    ak
rakurs     kurs                  kurs
rakur      kur                   нет
ak         k                     нет
kur        r                     нет

Правило

Выходная ссылка узла u равна его суффиксной ссылке, если та ведёт в помеченный узел; иначе она равна выходной ссылке того узла, куда ведёт суффиксная. Считается в том же обходе в ширину. При поиске на каждом символе сообщается слово текущего узла (если он помечен) и все слова по цепочке выходных ссылок. При выводе просматриваются только помеченные узлы - по одному на найденное вхождение. Полная цена: O(n + L + z), где L - сумма длин образцов, z - число вхождений.

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

Функция ssylki из прошлого урока теперь получает пометки konec, ведёт второй список vyhod и возвращает оба списка вместе с очередью обхода - она пригодится ниже:

def ssylki(deti, konec):
    ssyl = [0] * len(deti)
    vyhod = [0] * len(deti)               # 0 - выходной ссылки нет
    ochered = []
    for c in deti[0]:
        ochered.append(deti[0][c])
    g = 0
    while g < len(ochered):
        v = ochered[g]
        g = g + 1
        for c in deti[v]:
            u = deti[v][c]
            k = ssyl[v]
            while k > 0 and c not in deti[k]:
                k = ssyl[k]
            if c in deti[k]:
                k = deti[k][c]
            ssyl[u] = k
            if konec[k] >= 0:
                vyhod[u] = k              # суффиксная ссылка ведёт в слово
            else:
                vyhod[u] = vyhod[k]       # наследуем: у k она уже посчитана
            ochered.append(u)
    return [ssyl, vyhod, ochered]

Ноль в vyhod означает «ссылки нет»: корень словом не бывает. В функции poisk список vyhod приходит ещё одним параметром, а вместо одной проверки пометки после перехода стоит цикл:

        u = v
        if konec[u] < 0:
            u = vyhod[u]                  # сам узел не слово - сразу к ближайшему слову
        while u > 0:
            nashli.append([i, konec[u]])  # позиция конца и номер слова
            u = vyhod[u]

Прогон по rakursa:

позиция 2, узел rak:       rak, по выходной ссылке ak
позиция 5, узел rakurs:    rakurs, по выходной ссылке kurs
остальные позиции:         узел не помечен, выходной ссылки нет - ни одного шага

Найдены все четыре слова. Ответ на вопрос из начала урока: когда кончилось ak, поиск стоял в узле rak и в узел ak не заходил ни разу. О слове он узнал из записки на узле rak.

Позиция в ответе - это КОНЕЦ вхождения. Начало получается вычитанием: слово длины d, кончившееся в позиции i, началось в i − d + 1.

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

Данные из прошлого урока: текст из 10 000 символов, сто образцов по шесть символов.

алфавит    вхождений z    узлов просмотрено при выводе
                          цепочка суффиксных ссылок      выходные ссылки
   4           325                 32 280                      325
  26           100                 11 538                      100

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

Теперь граница. Образцы - a, aa, aaa и так до десяти букв a. Текст - тысяча букв a.

переходов по бору          1 990
найдено вхождений          9 955

В каждой позиции текста, начиная с десятой, кончаются все десять образцов сразу. Вхождений 1000 + 999 + … + 991 = 9955 - в пять раз больше, чем переходов. Это не недостаток алгоритма: ответ такого размера нельзя выдать быстрее, чем за его длину. Оценку, в которую входит размер ответа, называют чувствительной к выходу.

Если сами позиции не нужны, а нужно только ЧИСЛО вхождений каждого слова, z можно обойти. На проходе по тексту считаем, сколько раз поиск стоял в каждом узле: заводим список schet из нулей длиной в число узлов и после каждого перехода делаем schet[v] = schet[v] + 1. Потом идём по узлам в порядке, обратном обходу в ширину (это список ochered, который вернула ssylki), и прибавляем счётчик узла к счётчику узла по его суффиксной ссылке:

g = len(ochered) - 1
while g >= 0:
    u = ochered[g]
    schet[ssyl[u]] = schet[ssyl[u]] + schet[u]
    g = g - 1

После этого schet в узле слова равен числу его вхождений: для тех же десяти образцов получается 1000, 999, …, 991. Цена - длина текста плюс число узлов, и от z она не зависит.

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

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

Второе: одинаковые образцы в списке. В konec[v] помещается один номер. Если слово встречается в списке дважды, второй номер затирает первый, и первое слово «не находится». Либо список чистят от повторов до построения, либо в узле хранят список номеров.

Третье: позиция конца принята за позицию начала. Программа сообщает [5, 2] - в позиции 5 кончилось слово номер 2, kurs, - а подсветка в редакторе красит четыре символа НАЧИНАЯ с пятого. Длина слова берётся из списка образцов по номеру, начало - 5 − 4 + 1 = 2.

Четвёртое: ожидание линейного времени при любом ответе. Если образцы вложены друг в друга, вхождений может быть порядка n, умноженного на число образцов. Перед запуском на чужом списке слов стоит решить, нужны ли все позиции или хватит счётчиков.

Пятое: переходы через словарь там, где нужна скорость на символ. Уход по ссылкам даёт 2n в сумме, но отдельный символ может стоить многих переходов. Если нужна единица на символ, для каждого узла заранее считают переход по каждому символу алфавита - получается полный автомат из прошлой главы, и плата та же: память, равная числу узлов, умноженному на размер алфавита.

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

Первый сюжет - частоты. Сколько раз каждый из десяти тысяч терминов встречается в архиве документов? Позиции не нужны, вхождений миллионы. Счётчики по узлам и один проход по дереву ссылок дают ответ за время чтения архива.

Второй - тревога по первому совпадению. Фильтру на шлюзе не нужен список всех сигнатур в пакете: хватит одной. Тогда на узле хранят один бит «на цепочке есть слово» - это выходная ссылка, сжатая до признака, - и поиск останавливается на первом таком узле.

Третий - разметка текста. Чтобы расставить ссылки на все термины словаря, нужны и позиции, и длины, и решение, что делать с вложенными словами: rak внутри rakurs. Алгоритм честно сообщит оба; какое оставить - решает уже прикладной код, обычно в пользу самого длинного.

Теперь сам

Образцы - a, ba, aba. Расставь суффиксные и выходные ссылки. Затем прогони текст aba и перечисли все вхождения с позициями концов.

узел     суффиксная ссылка     выходная ссылка
a        корень                нет
ab       b                     нет              (b не помечен, у него выходной нет)
aba      ba                    ba               (ba помечен)
b        корень                нет
ba       a                     a                (a помечен)