Ответ 1

Испытания

В этой теме было четыре основных предложения:

• Шивам Калра предложил создать автомат на основе всех строк в A. Этот подход был слегка опробован в литературе, как правило, под названием "Направленный ациклический граф подпоследовательности" (DASG).

• J Random Hacker предложил расширить идею "префиксного списка" до всех "n выбрать 3" триплетов в строке запроса и слить их все с помощью кучи.

• В примечании "Эффективный поиск подпоследовательности в базах данных" Рохит Джайн, Мукеш К. Мохания и Сунил Прабхакар предлагают использовать структуру Trie с некоторыми оптимизациями и рекурсивно искать дерево для запроса. У них также есть предложение, подобное триплетной идее.

• Наконец, существует "наивный" подход, который wanghq предлагал оптимизировать, сохраняя индекс для каждого элемента A.

Чтобы получить лучшее представление о том, что стоит положить на продолжение усилий, я реализовал вышеупомянутые четыре подхода в Python и сравнил их по двум наборам данных. Реализации можно было бы сделать на несколько величин быстрее с хорошо выполненной реализацией на C или Java; и я не включил оптимизацию, предложенную для версий "trie" и "naive".

Тест 1

A состоит из случайных путей из моей файловой системы. q - 100 случайных строк [a-z] средней длины 7. Поскольку алфавит большой (а Python медленный), я мог использовать дуплеты для метода 3.

Время строительства в секундах в зависимости от размера A:

Время запроса в секундах в зависимости от размера A:

Тест 2

A состоит из случайных выборочных строк [a-b] длины 20. q - это 100 случайных строк [a-b] средней длины 7. Поскольку алфавит мал, мы можем использовать квадрики для метода 3.

Время строительства в секундах в зависимости от размера A:

Время запроса в секундах в зависимости от размера A:

Заключение

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

• Автоматы работают очень быстро при запросе (постоянное время), однако их невозможно создать и сохранить для |A| >= 256. Возможно, более тщательный анализ может дать лучший баланс времени/памяти или некоторые трюки, применимые для остальных методов.

• Метод dup/trip-/quadlet примерно в два раза быстрее, чем моя реализация trie, и в четыре раза быстрее, чем "наивная" реализация. Я использовал только линейное количество списков для слияния, вместо n^3, как было предложено j_random_hacker. Возможно, было бы лучше настроить метод лучше, но в целом это было неутешительно.

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

• Если вы можете делать с меньшей производительностью, наивный метод сравнительно просто подходит для очень небольших затрат.

Ответ 2

Это можно сделать, построив automaton. Вы можете начать с NFA (недетерминированный конечный автомат, который подобен индетерминированному ориентированному графу), который позволяет ребрам помечены символом epsilon, что означает, что во время обработки вы можете переходить от одного node к другому, не потребляя никакого символа. Я попытаюсь уменьшить ваш A. Скажем, вы A:

A = {'ab, 'bc'}

Если вы построите строку NFA для ab, вы должны получить что-то вроде этого:

     +--(1)--+ 
  e  |  a|   |e
(S)--+--(2)--+--(F)
     |  b|   |
     +--(3)--+

Выше рисунок - не самый красивый автомат. Но есть несколько моментов, которые следует учитывать:

• S Состояние - это начальное состояние, а F - конечное состояние.
• Если вы находитесь в состоянии F, это означает, что ваша строка соответствует подпоследовательности.
• Правило распространения внутри автомата заключается в том, что вы можете потреблять e (epsilon) для перехода вперёд, поэтому вы можете быть более чем одним состоянием в каждый момент времени. Это называется закрытием e.

Теперь, если задано b, начиная с состояния S, я могу прыгать на один epsilon, достигать 2 и потреблять b и достигать 3. Теперь, учитывая строку end, я потребляю epsilon и достигаю F, поэтому b квалифицируется как sub-sequence of ab. Таким образом, A или ab вы можете попробовать себя, используя вышеавтоматы.

Хорошая вещь о NFA заключается в том, что они имеют одно начальное состояние и одно конечное состояние. Два NFA могут быть легко связаны с помощью epsilons. Существуют различные алгоритмы, которые могут помочь вам преобразовать NFA в DFA. DFA - это ориентированный граф, который может следовать точному пути, заданному характером - в частности, он всегда находится в одном состоянии в любой момент времени. (Для любого NFA существует соответствующий DFA, состояния которого соответствуют наборам состояний в NFA.)

Итак, для A = {'ab, 'bc'} нам нужно было бы построить NFA для ab, затем NFA для bc, затем присоединиться к двум NFAs и построить DFA всего большого NFA.

ИЗМЕНИТЬ

NFA подпоследовательности abc будет a?b?c?, поэтому вы можете построить свой NFA как:

Теперь рассмотрим ввод acd. Чтобы запросить, если ab является подпоследовательностью {'abc', 'acd'}, вы можете использовать этот NFA: (a?b?c?)|(a?c?d). Когда у вас есть NFA, вы можете преобразовать его в DFA, где каждое состояние будет содержать то, является ли оно подпоследовательностью abc или acd или, возможно, и тем, и другим.

Я использовал ссылку ниже, чтобы сделать графику NFA из регулярного выражения:

http://hackingoff.com/images/re2nfa/2013-08-04_21-56-03_-0700-nfa.svg

EDIT 2

Вы правы! Если у вас есть 10 000 уникальных символов в A. Под уникальным я имею в виду, что A примерно так: {'abc', 'def'} то есть пересечение каждого элемента из A является пустым множеством. Тогда ваш DFA будет худшим случаем с точки зрения состояний, т.е. 2^10000. Но я не уверен, когда это возможно, учитывая, что никогда не может быть 10,000 уникальных символов. Даже если у вас есть 10 000 символов в A, все еще будут повторения, и это может значительно сократить количество состояний, поскольку в конечном итоге слияние может привести к слиянию. Я не могу оценить, насколько это может быть уменьшено. Но даже имея 10 миллионов штатов, вы будете потреблять менее 10 мб пространства для создания DFA. Вы даже можете использовать NFA и находить e-закрытия во время выполнения, но это добавит сложности во время выполнения. Вы можете искать различные документы о том, как большое регулярное выражение преобразуется в DFA.

РЕДАКТИРОВАТЬ 3

Для регулярного выражения (a?b?c?)|(e?d?a?)|(a?b?m?)

Если вы конвертируете над NFA в DFA, вы получаете:

На самом деле это намного меньше состояний, чем NFA.

Ссылка: http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

EDIT 4

После того, как поиграть с этим сайтом больше. Я обнаружил, что в худшем случае будет что-то вроде этого: A = {'aaaa', 'bbbbb', 'cccc'....}. Но даже в этом случае состояния меньше состояний NFA.

Ответ 3

Как вы заметили, возможно, что все строки в содержат q как подпоследовательность, и в этом случае вы не можете надеяться сделать лучше, чем O (| A |). (Тем не менее, вы все равно сможете сделать лучше, чем время, затраченное на выполнение LCS (q, A [i]) для каждой строки я в A, но я не буду здесь останавливаться на этом.)

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

Я предлагаю фильтрацию на основе обобщения вашей эвристики (2): если в какой-то последовательности базы данных A [i] содержится q как подпоследовательность, то она также должна содержать каждую подпоследовательность q. (Обратное направление неверно, к сожалению!) Итак, для небольшого k, например. 3, как вы полагаете, вы можете предварительно обработать, построив массив списков, сообщающий вам для каждой строки длины k строку списка последовательностей базы данных, содержащую s в качестве подпоследовательности. То есть c [s] будет содержать список идентификационных номеров последовательностей базы данных, содержащих s как подпоследовательность. Сохраните каждый список в числовом порядке, чтобы позже включить быстрые переходы.

Теперь основная идея (которую мы будем улучшать за один момент) для каждого запроса q: Найти все подпоследовательности k-размера q, искать каждый в массиве списков c [] и пересекать их чтобы найти множество последовательностей в A, которые могут содержать q как подпоследовательность. Тогда для каждой возможной последовательности A [i] в ​​этом (мы надеемся, малом) пересечении выполните вычисление LC (O2) LCS с q, чтобы увидеть, действительно ли оно содержит q.

Несколько наблюдений:

• Пересечение 2 отсортированных списков размером m и n можно найти в O (m + n) времени. Чтобы найти пересечение r-списков, выполните r-1 попарных пересечений в любом порядке. Так как прием пересечений может производить только меньшие или одинаковые размеры, время можно сохранить, сначала пересекая наименьшую пару списков, затем следующую наименьшую пару (это обязательно будет включать результат первой операции) и т.д., В частности: сортировать списки в порядке увеличения размера, а затем всегда пересекать следующий список с "текущим" пересечением.
  • На самом деле быстрее найти пересечение другим способом, добавив первый элемент (порядковый номер) каждого из r-списков в структуру данных кучи, затем многократно вытягивая минимальное значение и пополняя кучу следующим из списка, из которого был получен самый последний минимум. Это приведет к получению списка порядковых номеров в неубывающем порядке; любое значение, которое появляется меньше r раз подряд, может быть отброшено, так как оно не может быть членом всех r наборов.
• Если k-строка s имеет только несколько последовательностей в c [s], то она в некотором смысле является дискриминационной. Для большинства наборов данных не все k-строки будут одинаково различаться, и это может быть использовано в наших интересах. После предварительной обработки подумайте о том, чтобы отбросить все списки, имеющие более чем определенное фиксированное число (или некоторую фиксированную долю от общего количества) последовательностей по трем причинам:
  • Они занимают много места для хранения
  • Они занимают много времени, чтобы пересекаться во время обработки запросов
  • Пересечение их обычно не будет сильно сокращать общее пересечение.
• Нет необходимости рассматривать каждую k-подпоследовательность q. Хотя это приведет к наименьшему пересечению, оно включает в себя объединение (| q | выбрать k) списков, и вполне возможно создать пересечение, которое почти так же мало, используя только часть этих k-подпоследовательностей. Например. вы можете ограничить себя попыткой всех (или нескольких) k-подстрок q. В качестве дополнительного фильтра рассмотрим только те k-подпоследовательности, списки последовательностей которых в c [s] ниже некоторого значения. (Примечание: если ваш порог для каждого запроса одинаковый, вы можете также удалить все такие списки из базы данных, так как это будет иметь тот же эффект и сэкономит место.)

Ответ 4

Одна мысль;
если q имеет тенденцию быть коротким, возможно, сокращение A и q до набора поможет?
Итак, для примера получим {(a, b, c, d, e, f), (a), (a, c, d)}. Поиск возможных кандидатов для любого q должен быть быстрее, чем исходная проблема (что догадка на самом деле, не знаю, как именно. Может быть, сортировать их и "группировать" аналогичные в фильтрах цветка?), А затем использовать bruteforce для отсечения ложных срабатываний.
Если строки длинны, вы можете сделать символы уникальными в зависимости от их появления, так что это будет {(a1, b1, c1, d1, e1, f1), (a1, a2, a3, a4, a5, а6), (a1, c1, d1, d2)}. Это хорошо, потому что, если вы ищете "ddca", вы хотите только совместить второй d со второй d. Размер вашего алфавита повысился (плохо для операций цветения или растрового стиля) и будет отличаться при каждом появлении новых A, но количество ложных срабатываний будет уменьшаться.

Ответ 5

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

• если A - подпоследовательность B, то все символы из A должны появиться в B.
• для этих символов в B, их позиции должны быть в порядке возрастания.

Обратите внимание, что a char в может появляться более одного раза в B.

Чтобы решить 1), можно использовать карту/множество. Ключ - это символ в строке B, и значение не имеет значения. Чтобы решить 2), нам нужно сохранить положение каждого персонажа. Поскольку символ может появляться более одного раза, позиция должна быть сборкой.

Итак, структура похожа:

Map<Character, List<Integer>)
e.g.
abcdefab
a: [0, 6]
b: [1, 7]
c: [2]
d: [3]
e: [4]
f: [5]

Как только у нас есть структура, как узнать, находятся ли символы в правильном порядке, так как они находятся в строке A? Если B - acd, мы должны проверить A в позиции 0 (но не 6), c в позиции 2 и d в позиции 3.

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

public E higher(E e)
Returns the least element in this set strictly greater than the given element, or null if there is no such element.

Сложность выполнения - это O (s * (n1 + n2) * log (m))).

• s: количество строк в наборе
• n1: количество символов в строке (B)
• n2: количество символов в строке запроса (A)
• m: количество дубликатов в строке (B), например. существует 5 A.

Ниже приведена реализация с некоторыми тестовыми данными.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

public class SubsequenceStr {

    public static void main(String[] args) {
        String[] testSet = new String[] {
            "abcdefgh", //right one
            "adcefgh", //has all chars, but not the right order
            "bcdefh", //missing one char
            "", //empty
            "acdh",//exact match
            "acd",
            "acdehacdeh"
        };
        List<String> subseqenceStrs = subsequenceStrs(testSet, "acdh");
        for (String str : subseqenceStrs) {
            System.out.println(str);
        }
        //duplicates in query
        subseqenceStrs = subsequenceStrs(testSet, "aa");
        for (String str : subseqenceStrs) {
            System.out.println(str);
        }
        subseqenceStrs = subsequenceStrs(testSet, "aaa");
        for (String str : subseqenceStrs) {
            System.out.println(str);
        }
    }

    public static List<String> subsequenceStrs(String[] strSet, String q) {
        System.out.println("find strings whose subsequence string is " + q);
        List<String> results = new ArrayList<String>();
        for (String str : strSet) {
            char[] chars = str.toCharArray();
            Map<Character, TreeSet<Integer>> charPositions = new HashMap<Character, TreeSet<Integer>>();
            for (int i = 0; i < chars.length; i++) {
                TreeSet<Integer> positions = charPositions.get(chars[i]);
                if (positions == null) {
                    positions = new TreeSet<Integer>();
                    charPositions.put(chars[i], positions);
                }
                positions.add(i);
            }
            char[] qChars = q.toCharArray();
            int lowestPosition = -1;
            boolean isSubsequence = false;
            for (int i = 0; i < qChars.length; i++) {
                TreeSet<Integer> positions = charPositions.get(qChars[i]);
                if (positions == null || positions.size() == 0) {
                    break;
                } else {
                    Integer position = positions.higher(lowestPosition);
                    if (position == null) {
                        break;
                    } else {
                        lowestPosition = position;
                        if (i == qChars.length - 1) {
                            isSubsequence = true;
                        }
                    }
                }
            }
            if (isSubsequence) {
                results.add(str);
            }
        }
        return results;
    }
}

Вывод:

find strings whose subsequence string is acdh
abcdefgh
acdh
acdehacdeh
find strings whose subsequence string is aa
acdehacdeh
find strings whose subsequence string is aaa

Как всегда, я могу быть абсолютно неправ:)

Ответ 6

Возможно, вам стоит взглянуть на алгоритмы книги по строкам и последовательностям Дэн Гусфилд. Как выясняется, часть его доступна в Интернете. Вы также можете прочитать Gusfield Введение в деревья суффикса. Как оказалось, эта книга охватывает множество подходов к вам, вопрос. Он считается одним из стандартных публикаций в этой области.

• Быстрое выполнение самой длинной общей подпоследовательности. На самом деле достаточно определить длину LCS. Обратите внимание, что книга Гусмана имеет очень хорошие алгоритмы, а также указывает на большее количество источников для таких алгоритмов.
• Вернуть все s ∈ A с помощью length(LCS(s,q)) == length(q)