Существует ли алгоритм лучшего крона, чтобы генерировать график, отношение которого является String Rized= 1?

Question

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

Очевидный подход - сделать все $ \ frac {n ^ 2-n} {2} $ Сравнение среди $ n $ вершины, давая нам $ O (n ^ 2) $ Сложность времени.

За исключением параллелизации сравнений, есть лучший алгоритм с точки зрения сложности времени?

Я заинтересован в строковых метриках, где разрешены строки разной длины.

Answer 1

В худшем случае любой такой алгоритм будет работать $ \ Omega (n ^ 2) $ потому что ваш график может иметь $ \ Omega (n ^ 2) $ ребра.

Кстати, вы заинтересованы в какой-то конкретной метрике строки?

Answer 2

Можно использовать BK-деревья , чтобы ускорить это. Вставка $ n $ Элементы в дереве принимает $ O (n \ log n) $ время. После этого вы можете запрашивать дерево для всех струн, расстояние редактирования которых является ровно от вашего ввода. Делать это для всех строк, снова требует $ o (n ^ 2) $ Сложность, однако, с очень небольшим постоянным фактором ( Эта страница упоминается только 5-8% дерева, необходимо проверить на запрос ).

Вот краткое описание того, как он работает:

Структура данных

BK-дерево либо

.
• пустой
• Узел с корневым значением $ R $ и набор индексированных детей $ C_I $ , каждый бК-дерево (реализован с использованием карт HASH, динамический массив или аналогичный)

Метрика (важная!) Функция расстояния $ d (x, y) $ используется для вставки и запросов.

вставка строки $ S $

.
• Если дерево пустое, сделайте его новым узлом с $ S $ в качестве корневой стоимости и нет детей
• Если дерево является узлом с root $ R $ и детей $ C_I $ , пусть < SPAN CLASS= «Математический контейнер»> $ k= d (r, s) $ .
  .
  • Если $ k= 0 $ , пропустить вставку как $ s $ уже в корне < / li>
  • В противном случае рекурсивно вставка $ S $ в $ k $ -th> «Математический контейнер»> $ C_K $ .

Последний шаг гарантирует, что все узлы в $ C_I $ имеют расстояние $ i $ к root

Запрос строки $ S $

.
• Если дерево пустое, верните никаких результатов
• Если дерево является узлом с root $ R $ и детей $ C_I $ , пусть < SPAN CLASS= «Математический контейнер»> $ k= d (r, s) $ .
  .
  • Если $ k= 1 $ , добавьте $ R $ в результате ( примечание : этот шаг отличается от обычных запросов BK-деревьев)
  • Кроме того, рекурсивно запрос $ S $ от детей $ C_ {D-1} $ , $ C_D $ и $ C_ {d + 1} $ . Верните все результаты из этих запросов, а также>

Последний шаг Существует волшебство BK-деревьев, так как ему не нужно проверять других детей из-за метрики расстояния. Вот частичное доказательство того, почему другие не нужно проверять:

Давайте предположим, что есть некоторая строка $ x $ , который имеет расстояние один из нашего запроса, поэтому $ D (S, x)= 1 $ , но это в дочернем дереве $ C_ {k + 2} $ . Мы знаем, что $ d (R, X)= K + 2 $ из процедуры вставки. Это, однако (с неравенством треугольника для метрических пространств) дает

$$ k + 2= d (r, x) \ leq d (r, s) + d (s, x)= k + 1 $$

Но это противоречие! Подобные могут быть сделаны для всех детей с $ I> K + 1 $ и $ i Это означает, что все строки у других детей не будут иметь расстояния один по конструкции, поэтому нам не нужно даже проверять их, что экономит время обработки.

Редактировать: другое объяснение: https://signal-to-noise.xyz / post / bk-tree /