Longest Common Substring

В данной заметке я опишу алгоритм решения задачи наибольшей общей подстроки. Допустим мы пытаемся расшифровать зашифрованные бинарные данные, для начала попробуем найти общие паттерны с помощью поиска наибольшей подстроки.
Входная строка для примера:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Мы ищем повторяющуюся дважды строку:
DATAHEADER??

Префиксы

Для начала напишем метод для сравнения префиксов двух строк, пусть возвращает результирующую строку в которой символы левого префикса равны символам правого префикса.
Например для строк:


        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

Результирующая строка – asdf
Пример на Kotlin:


fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Brute Force

Когда не получается по хорошему, стоит прибегнуть к грубой силе. Используя метод longestPrefix пройдем по строке двумя циклами, первый берет строку от i до конца, второй от i + 1 до конца, передает их в поиск наибольшего префикса. Временная сложность данного алгоритма примерно равна O(n^2) ~ O(n*^3).
Пример на Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Суффиксный массив

Для более элегантного решения нам потребуется инструмент - структура данных под названием “Суффиксный массив”. Данная структура данных представляет из себя массив из подстрок заполняемых в цикле, где каждая подстрока начинается со следующего символа строки до конца.
Например для строки:


adasDATAHEADER??

Суффиксный массив выглядит так:


adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

Решаем сортировкой

Отсортируем суффиксный массив, затем пройдем по всем элементам циклом где в левой руке (lhs) текущий элемент, в правой (rhs) следующий и вычислим самый длинный префикс с помощью метода longestPrefix.
Пример на Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

Временная сложность алгоритма O(N log N), что гораздо лучше решения в лоб.

Источники

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Исходный код

https://gitlab.com/demensdeum/algorithms

0

Insertion Sort, Merge Sort

Insertion Sort

Сортировка вставками – каждый элемент сравнивается с предыдущими по списку и элемент вставляется на место большего. Так как элементы сортируются с первого по последний, то каждый следующий элемент сравнивается с уже отсортированным списком, что *возможно* уменьшит общее время работы. Временная сложность алгоритма O(n^2), то есть идентична баббл сорту.

Merge Sort

Сортировка слиянием – список разделяется на группы по одному элементу, затем группы “сливаются” попарно с одновременным сравнением. В моей реализации при слиянии пар элементы слева сравниваются с элементами справа, затем перемещаются в результирующий список, если элементы слева закончились, то происходит добавление всех элементов справа в результирующий список (их дополнительное сравнение излишне, так как все элементы в группах проходят итерации сортировки)
Работу данного алгоритма очень легко распараллелить, этап слияния пар можно выполнять в потоках, с ожиданием окончания итераций в диспетчере.
Вывод алгоритма для однопоточного выполнения:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Вывод алгоритма для многопоточного выполнения:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Временная сложность алгоритма O(n*log(n)), что немного лучше чем O(n^2)

Источники

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

Исходный код

https://gitlab.com/demensdeum/algorithms

0

Сортировка пузырьком на Erlang

Сортировка пузырьком это достаточно скучно, но становится интереснее если попробовать реализовать его на функциональном языке для телекома – Erlang.

У нас есть список из цифр, нам нужно его отсортировать. Алгоритм сортировки пузырьком проходит по всему списку, итерируя и сравнивая числа попарно. На проверке происходит следующее: меньшее число добавляется в выходной список, либо числа меняются местами в текущем списке если справа меньше, перебор продолжается со следующим по итерации числом. Данный обход повторяется до тех пор, пока в списке больше не будет замен.

На практике его использовать не стоит из-за большой временной сложности алгоритма – O(n^2); я реализовал его на языке Erlang, в императивном стиле, но если вам интересно то можете поискать лучшие варианты:


-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Установка и запуск

В Ubuntu Эрланг установить очень просто, достаточно в терминале набрать команду sudo apt install erlang. В данном языке каждый файл должен представлять из себя модуль (module), со списком функций которые можно использовать извне – export. К интересным особенностям языка относится отсутствие переменных, только константы, отсутствие стандартного синтаксиса для ООП (что не мешает использовать ООП техники), и конечно же параллельные вычисления без блокировок на основе модели акторов.

Запустить модуль можно либо через интерактивную консоль erl, запуская одну команду за другой, либо проще через escript bubbleSort.erl; Для разных случаев файл будет выглядеть по разному, например для escript необходимо сделать функцию main, из которой он будет стартовать.

Источники

https://www.erlang.org/
https://habr.com/ru/post/197364/

Исходный код

https://gitlab.com/demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl

0

Алгоритм лексикографического сравнения

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

Пример для языка Си можно посмотреть здесь:
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

Следует учитывать что сравнивать символы нужно в единой статичной кодировке, например в Swift я использовал посимвольное сравнение на UTF-32. Вариант сортировки массива с использованием memcmp сработает точно для однобайтовых символов, в остальных случаях (кодировки переменной длины) возможно порядок будет некорректен. Не исключаю возможности реализации на основе кодировок переменной длины, но скорее всего будет на порядок сложнее.

Временная сложность алгоритма в лучшем случае O(1), среднем и худшем O(n)

Источники

https://ru.wikipedia.org/wiki/Лексикографический_порядок

Исходники

https://gitlab.com/demensdeum/algorithms/blob/master/lexiCompare/lexiCompare.swift

0

Двоичный поиск

Допустим нам необходимо узнать относится ли адрес электронной почты “demensdeum@gmail.com”  к списку разрешенных email адресов для получения писем.

Переберем весь список от первого до последнего элемента, проверяя равен ли элемент указанному адресу – реализуем алгоритм линейного поиска. Но это же будет долго, или не будет?

Для ответа на этот вопрос используют “Временную сложность алгоритмов”, “О” нотацию. Время работы линейного поиска в худшем случае равно n-му количеству элементов массива, напишем это в “О” нотации – O(n). Далее нужно пояснить что для любого известного алгоритма есть три показателя производительности – время выполнения в лучшем, худшем и среднем случае. Например адрес почты “demensdeum@gmail.com” находится в первом индексе массива, тогда он будет найден за первый шаг алгоритма, из этого следует что время выполнения в лучшем случае – O(1); а если в конце списка, то это худший случай – O(n)

Но как же детали реализации ПО, производительность железа, они ведь должны влиять на big O? А теперь выдохните и представьте что расчет временной сложности рассчитывается для некой абстрактной идеальной машины, в которой есть только этот алгоритм и больше ничего.

Алгоритм

Ок, получается что линейный поиск достаточно медленный, попробуем использовать Бинарный поиск. Для начала следует пояснить что с бинарными данными мы работать не будем, такое название данному методу дано из-за особенностей его работы. Изначально мы сортируем массив в лексикографическом порядке, затем алгоритм берет диапазон всего массива, получает средний элемент диапазона, сравнивает его лексикографически, и в зависимости от результата сравнения решает какой диапазон брать для поиска дальше – верхнюю половину текущего или нижнюю. То есть на каждом шаге поиска принимается решение из двух возможных – бинарная логика. Этот шаг повторяется до тех пор, пока либо слово найдется, либо не найдется (произойдет пересечение нижнего и верхних индексов диапазона).

Производительность данного алгоритма – лучший случай когда сразу найден элемент в середине массива O(1), худший случай перебора O(log n)

Подводные камни

При реализации бинарного поиска я встретился мало того с интересной проблемой отсутствия стандартизации лексикографического сравнения в библиотеках языков программирования, но даже обнаружил отсутствие единого стандарта реализации localeCompare внутри JavaScript. Стандарт ECMAScript допускает разную реализацию данной функции, из-за этого при сортировке с помощью localeCompare, на разных движках JavaScript может наблюдаться абсолютно разный результат.

Поэтому для корректной работы алгоритма нужно обязательно сортировать и использовать в работе только один и тот же алгоритм лексикографического сравнения, иначе работать ничего не будет. Со-но если например попытаться сортировать массив в Scala, а искать с помощью nodejs, не реализуя собственную сортировку/сортировку одной реализации, то кроме разочарования в человечестве вас ничего не ждет.

Источники

Что такое лексикографическое сравнение и что оно собой представляет?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript

Исходный код

https://gitlab.com/demensdeum/algorithms

0