Автомат Кнута-Морриса-Пратта

В этой главе приведено три реализации автомата КМП, описанного в конце прошлой главы.

Наивная реализация

Наивная реализация состоит в представлении автомата его функцией перехода:

function step(automaton, state, letter) {
    return automaton(state,letter)
}

Тривиальный автомат (для распознавания пустого текста) устроен так:

function trivial_automaton() { return (s,l) => s }

Он переводит каждое состояние в себя. В частности, состояние 0, независимо от входной буквы, переходит в себя.

Индуктивная функция построения устроена так:

// здесь n -- номер шага процедуры построения
function update_automaton(n, automaton, letter) {
    function new_automaton(s,l) {
        if (s < n)  { return automaton(s,l) }
        if (s == n) { return l==letter ? n+1 : automaton(s,l) }
        return new_automaton(automaton(n,letter),l)
    }

    return new_automaton
}

Основной её недостаток (исключающий возможность практического применения наивного автомата КМП) – длительность поиска состояния в построенном автомате. Например, автомат, построенный на k-м шаге, при подаче ему на вход состояния 0 будет вынужден сделать рекуррентный вызов глубины k. Тем не менее, наивный автомат всё же служит хорошей иллюстрацией, на основе которой можно реализовать более эффективный автомат.

Закончим представление наивного автомата функциями построения и поиска:

function build_automaton(text) {
    let aut = trivial_automaton()
    
    for (let n = 0; n < text.length; n++) {
        aut = update_automaton(n, aut, text[n])
    }

    return aut
}

function search(needle, haystack) {
    if (!needle) { return 0 }

    let aut = build_automaton(needle)

    let s = 0
    for (let i = 0; i < haystack.length; i++) {
        s = step(aut, s, haystack[i])

        if (s == needle.length) { return i-needle.length+1 }
    }

    return -1
}

Автомат на основе массива

Довольно эффективной, правда, существенно более сложной является реализация на основе массива.

function step(automaton, state, letter) {
    return automaton[state][ord(letter)]
}

Здесь ord – функция, сопоставляющая букве её код. Одна из возможных реализаций ord вместе с обратным преобразованием:

function ord(char) { return char.codePointAt(0) }
function chr(code) { return String.fromCodePoint([code]) }

Функция построения тривиального автомата теперь требует на вход алфавит:

function trivial_automaton(alphabet) {
    let result = [[]]

    for (let a of alphabet) { result[0][ord(a)] = 0 }

    return result
}

Зато шаг индукции уже не требует номер шага:

function update_automaton(automaton, letter) {
    let n = automaton.length-1
    let code = ord(letter)
    
    // далее _очень_ важен порядок действий
    let state_to_copy = automaton[n][code]
    automaton[n][code] = n+1
    automaton[n+1] = automaton[state_to_copy].slice()
}

Построение и поиск почти не отличаются от вариантов для наивного автомата:

function build_automaton(alphabet, text) {
    let aut = trivial_automaton(alphabet)
    
    for (let x of text) { update_automaton(aut, x) }

    return aut
}

function search(needle, haystack) {
    if (!needle) { return 0 }

    // Алфавит легко вычисляется ---.
    //                              V
    //                        ...............
    let aut = build_automaton(needle+haystack, needle)

    let s = 0
    for (let i = 0; i < haystack.length; i++) {
        s = step(aut, s, haystack[i])

        if (s == needle.length) { return i-needle.length+1 }
    }

    return -1
}

Алфавит на основе иммутабельных отображений

В заключение приведём один из наиболее простых вариантов реализации КМП, использующий иммутабельные отображения (ассоциативные массивы). По своей сути это наивный автомат, все переходы которого предварительно вычислены.

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

<script src="путь_к_файлу"></script>

Автомат устроен так:

IMap = Immutable.Map  // Сокращение, чтобы не путать со встроенным типом Map

function step(automaton, state, letter) {
    return automaton.get(state).get(letter)
}

function trivial_automaton(alphabet) { 
    let triv_map = IMap()

    for (let x of alphabet) { triv_map = triv_map.set(x, 0) }

    return IMap().set(0, triv_map)
 }

Отметим, что операция set не изменяет ассоциативный массив, к которому она применена, а создаёт новый на основе старого.

function update_automaton(automaton, letter) {
    let n = automaton.size - 1

    // t(b(n),n) = n+1
    let end = automaton.get(n).set(letter, n+1)
    let aut = automaton.set(n, end)
 
    // t(x,n+1)  = t(x,T(b(n),n))
    return aut.set(n+1, aut.get(step(automaton, n, letter)))
}

Из всех приведённых в этой главе реализаций эта наиболее близка к математической модели из прошлой главы. Для полноты картины приведём функцию построения автомата (функцию поиска приводить не будем, поскольку она полностью идентична таковой для реализации на основе массива).

function build_automaton(alphabet, text) {
    let aut = trivial_automaton(alphabet)
    
    for (let x of text) { aut = update_automaton(aut, x) }

    return aut
}