Алгоритм найти самый маленький фрагмент из поиска документа?

Question

Я изучал превосходное «Руководство по разработке алгоритмов» Скиены и зациклился на одном из упражнений.

Вопрос в следующем: «Учитывая строку поиска из трех слов, найдите наименьший фрагмент документа, который содержит все три поисковых слова, то есть фрагмент с наименьшим количеством слов в нем. Вам даны позиции индекса, где эти слова встречаются в поисковых строках , например word1: (1, 4, 5), word2: (4, 9, 10) и word3: (5, 6, 15). Каждый из списков находится в отсортированном порядке, как указано выше. "

Все, что я придумаю, это O (n ^ 2) ... Этот вопрос находится в главе "Сортировка и поиск", поэтому я предполагаю, что есть простой и умный способ сделать это. Я сейчас что-то пробую с графиками, но это кажется излишним.

Идеи? Спасибо

Answer 1

Если я что-то не заметил, вот простой алгоритм O (n):

1. Мы представим фрагмент с помощью (x, y), где x и y - то, где фрагмент начинается и заканчивается соответственно.
2. Фрагмент возможен, если он содержит все 3 поисковых слова.
3. Начнем с недопустимого фрагмента (0,0).
4. Повторяйте следующее, пока y не достигнет конца строки:
   5. Если текущий фрагмент (x, y) выполним, перейдите к фрагменту (x + 1, y)
      Остальное (текущий фрагмент невозможен) перейти к фрагменту (x, y + 1)
5. Выберите самый короткий фрагмент из всех возможных фрагментов, через которые мы прошли.

Продолжительность - в каждой итерации x или y увеличивается на 1, очевидно, что x не может превышать y, а y не может превышать длину строки, поэтому общее количество итераций равно O (n). Кроме того, выполнимость может быть проверена в O (1) в этом случае, так как мы можем отследить, сколько вхождений каждого слова находится в текущем фрагменте. Мы можем поддерживать этот счет на уровне O (1) с каждым увеличением x или y на 1.

Корректность - Для каждого x мы вычисляем минимально допустимый фрагмент (x,?). Таким образом, мы должны перейти к минимальному фрагменту. Кроме того, если у - наименьшее у, такое, что (x, y) выполнимо, то, если (x + 1, y ') - допустимый фрагмент, y'> = y (этот бит - то, почему этот алгоритм является линейным, а остальные не т).

Answer 2

Я уже опубликовал довольно простой алгоритм, который решает именно эту проблему в этом ответе

Результаты поиска Google: Как найти минимальное окно, содержащее все ключевые слова для поиска?

Однако в этом вопросе мы предположили, что входные данные представлены текстовым потоком, а слова хранятся в удобном для поиска наборе.

В вашем случае вход представляется немного по-другому: как набор векторов с отсортированными позициями для каждого слова. Это представление легко трансформируется в то, что необходимо для вышеуказанного алгоритма, просто объединяя все эти векторы в один вектор из (position, word) пар, упорядоченных по позиции. Это можно сделать буквально или «виртуально», поместив исходные векторы в приоритетную очередь (упорядоченную в соответствии с их первыми элементами). Удаление элемента из очереди в этом случае означает извлечение первого элемента из первого вектора в очереди и, возможно, погружение первого вектора в очередь в соответствии с его новым первым элементом.

Конечно, поскольку ваша постановка задачи явно фиксирует количество слов как three , вы можете просто проверить первые элементы всех трех массивов и вытолкнуть наименьший из них на каждой итерации. Это дает вам алгоритм O(N), где N - общая длина всех массивов.

Кроме того, ваше утверждение проблемы, по-видимому, предполагает, что целевые слова могут перекрываться в тексте, что довольно странно (учитывая, что вы используете термин «слово»). Это намеренно? В любом случае, это не представляет проблемы для вышеуказанного связанного алгоритма.

Answer 3

Судя по этому вопросу, вы, похоже, указали местоположения индекса для каждого из ваших n «поисковых слов» (word1, word2, word3, ..., word n ) в документе.Используя алгоритм сортировки, независимые массивы n , связанные с поисковыми словами, могут быть легко представлены в виде единого массива всех позиций индекса в возрастающем числовом порядке и метки слова, связанной с каждым индексом в массиве (индексмассив).

Основной алгоритм:

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

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

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

Необходимые оптимизации:

1. Отслеживайте значение текущей длины самого короткого фрагмента, чтобы значение было известно сразу после итерации по массиву индекса.
2. При итерации по вашему массиву завершите функцию длины фрагмента, если текущийпроверяемый фрагмент всегда превосходит длину самой короткой длины фрагмента, замеченной ранее.
3. Когда функция длины фрагмента возвращает ноль, так как не находит все n поисковых слов в оставшихся элементах массива индекса, свяжитенулевая длина фрагмента для всех последовательных элементов в массиве индекса.
4. Если функция длины фрагмента применяется к метке слова, а метка, следующая непосредственно за ней, идентична начальной метке, присвойте нулевую величину начальной меткеи перейти кследующая метка.

Вычислительная сложность:

Очевидно, что сортирующая часть алгоритма может быть организована в O ( n log n ).

Вот как я бы рассчитал временную сложность второй части алгоритма (любые критические замечания и исправления были бы очень полезны).

В лучшем случае алгоритм применяет функцию длины фрагмента только к первому элементу в массиве индексов и обнаруживает, что не существует фрагмента, содержащего все искомые слова. Этот сценарий будет рассчитан всего за n вычислений, где n - размер массива индекса. Чуть хуже, если самый маленький фрагмент окажется равным размеру всего массива. В этом случае вычислительная сложность будет чуть меньше 2 n (один раз через массив найти минимальную длину фрагмента, второй раз продемонстрировать, что других фрагментов не существует). Чем короче средняя вычисленная длина фрагмента, тем больше раз необходимо будет применить функцию длины фрагмента к массиву индекса. Мы можем предположить, что в нашем худшем сценарии будет применена функция длины фрагмента к каждому элементу в массиве индекса. Чтобы разработать случай, когда функция будет применяться к каждому элементу в массиве индекса, нам нужно спроектировать индексный массив, где средняя длина фрагмента по всему массиву индекса незначительна по сравнению с размером массива индекса в целом. Используя этот случай, мы можем записать нашу вычислительную сложность как O (C n ), где C - некоторая постоянная, которая значительно меньше, чем n . Дать окончательную вычислительную сложность:

O ( n log n + C n )

Где:

C << <em>n

Edit:

AndreyT правильно указывает, что вместо сортировки показаний слов во время n log n , их можно также объединить (так как подмассивы уже отсортированы) в n log m время, где m - количество массивов поисковых слов, которые должны быть объединены. Это, очевидно, ускорит алгоритм в тех случаях, когда m <<em> n .

Answer 4

O (n log k) решение, где n - общее количество индексов, а k - количество слов. Идея состоит в том, чтобы использовать кучу для определения наименьшего индекса на каждой итерации, а также отслеживать максимальный индекс в куче. Я также поместил координаты каждого значения в кучу, чтобы иметь возможность получить следующее значение за постоянное время.

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>

using namespace std;

int snippet(const vector< vector<int> >& index) {
    // (-index[i][j], (i, j))
    priority_queue< pair< int, pair<size_t, size_t> > > queue;
    int nmax = numeric_limits<int>::min();
    for (size_t i = 0; i < index.size(); ++i) {
        if (!index[i].empty()) {
            int cur = index[i][0];
            nmax = max(nmax, cur);
            queue.push(make_pair(-cur, make_pair(i, 0)));
        }
    }
    int result = numeric_limits<int>::max();
    while (queue.size() == index.size()) {
        int nmin = -queue.top().first;
        size_t i = queue.top().second.first;
        size_t j = queue.top().second.second;
        queue.pop();
        result = min(result, nmax - nmin + 1);
        j++;
        if (j < index[i].size()) {
            int next = index[i][j];
            nmax = max(nmax, next);
            queue.push(make_pair(-next, make_pair(i, j)));
        }
    }
    return result;
}

int main() {
    int data[][3] = {{1, 4, 5}, {4, 9, 10}, {5, 6, 15}};
    vector<vector<int> > index;
    for (int i = 0; i < 3; i++) {
        index.push_back(vector<int>(data[i], data[i] + 3));
    }
    assert(snippet(index) == 2);
} 

Answer 5

Пример реализации в Java (протестировано только с реализацией в примере, могут быть ошибки). Реализация основана на ответах выше.

import java.util.Arrays;


public class SmallestSnippet {
    WordIndex[] words; //merged array of word occurences

    public enum Word {W1, W2, W3};

    public SmallestSnippet(Integer[] word1, Integer[] word2, Integer[] word3) {
        this.words = new WordIndex[word1.length + word2.length + word3.length];
        merge(word1, word2, word3);
        System.out.println(Arrays.toString(words));
    }

    private void merge(Integer[] word1, Integer[] word2, Integer[] word3) {
        int i1 = 0;
        int i2 = 0;
        int i3 = 0;
        int wordIdx = 0;
        while(i1 < word1.length || i2 < word2.length || i3 < word3.length) {
            WordIndex wordIndex = null;
            Word word = getMin(word1, i1, word2, i2, word3, i3);
            if (word == Word.W1) {
                wordIndex = new WordIndex(word, word1[i1++]);
            }
            else if (word == Word.W2) {
                wordIndex = new WordIndex(word, word2[i2++]);
            }
            else {
                wordIndex = new WordIndex(word, word3[i3++]);
            }
            words[wordIdx++] = wordIndex;
        }       
    }

    //determine which word has the smallest index
    private Word getMin(Integer[] word1, int i1, Integer[] word2, int i2, Integer[] word3,
            int i3) {
        Word toReturn = Word.W1;
        if (i1 == word1.length || (i2 < word2.length && word2[i2] < word1[i1])) {
            toReturn  = Word.W2;
        }
        if (toReturn == Word.W1 && i3 < word3.length && word3[i3] < word1[i1])
        {
            toReturn = Word.W3;
        }
        else if (toReturn == Word.W2){
            if (i2 == word2.length || (i3 < word3.length && word3[i3] < word2[i2])) {
                toReturn = Word.W3;
            }
        }
        return toReturn;
    }

    private Snippet calculate() {
        int start = 0;
        int end = 0;
        int max = words.length;
        Snippet minimum = new Snippet(words[0].getIndex(), words[max-1].getIndex());
        while (start < max)
        {
            end = start;
            boolean foundAll = false;
            boolean found[] = new boolean[Word.values().length];
            while (end < max && !foundAll) {
                found[words[end].getWord().ordinal()] = true;
                boolean complete = true;
                for (int i=0 ; i < found.length && complete; i++) {
                    complete = found[i];
                }
                if (complete)
                {
                    foundAll = true;
                }
                else {
                    if (words[end].getIndex()-words[start].getIndex() == minimum.getLength())
                    {
                        // we won't find a minimum no need to search further
                        break;
                    }
                    end++;
                }
            }
            if (foundAll && words[end].getIndex()-words[start].getIndex() < minimum.getLength()) {
                minimum.setEnd(words[end].getIndex());
                minimum.setStart(words[start].getIndex());
            }
            start++;
        }
        return minimum;

    }


    /**
     * @param args
     */
    public static void main(String[] args) {
        Integer[] word1 = {1,4,5};
        Integer[] word2 = {3,9,10};
        Integer[] word3 = {2,6,15};
        SmallestSnippet smallestSnippet = new SmallestSnippet(word1, word2, word3);
        Snippet snippet = smallestSnippet.calculate();
        System.out.println(snippet);

    }
}

Вспомогательные классы:

public class Snippet {

    private int start;

    private int end;

//getters, setters etc

    public int getLength()
    {
        return Math.abs(end - start);
    }
}



public class WordIndex
{
    private SmallestSnippet.Word word;
    private int index;
    public WordIndex(SmallestSnippet.Word word, int index) {

        this.word = word;
        this.index = index;
    }
}

Answer 6

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

Учитывая три набора целых чисел (назовите их A, B и C), найдите минимальный непрерывный диапазон, который содержит один элемент из каждого набора.

Существует некоторая путаница в отношении того, что представляют собой три набора. Во втором издании книги они обозначены как {1, 4, 5}, {4, 9, 10} и {5, 6, 15}. Тем не менее, другая версия, которая была изложена в комментарии выше, это {1, 4, 5}, {3, 9, 10} и {2, 6, 15}. Если одно слово не является суффиксом / префиксом другого, версия 1 невозможна, поэтому давайте перейдем ко второму.

Поскольку картинка стоит тысячи слов, давайте начертим точки:

Простая визуальная проверка вышесказанного показывает, что есть два ответа на этот вопрос: [1,3] и [2,4], оба размера 3 (три точки в каждом диапазоне).

Теперь алгоритм. Идея состоит в том, чтобы начать с наименьшего допустимого диапазона и постепенно пытаться уменьшить его, перемещая левую границу внутрь. Мы будем использовать индексацию с нуля.

MIN-RANGE(A, B, C)
  i = j = k = 0
  minSize = +∞

  while i, j, k is a valid index of the respective arrays, do
    ans = (A[i], B[j], C[k])
    size = max(ans) - min(ans) + 1
    minSize = min(size, minSize)
    x = argmin(ans)
    increment x by 1
  done

  return minSize

где argmin - индекс наименьшего элемента в ans.

+---+---+---+---+--------------------+---------+
| n | i | j | k | (A[i], B[j], C[k]) | minSize |
+---+---+---+---+--------------------+---------+
| 1 | 0 | 0 | 0 | (1, 3, 2)          | 3       |
+---+---+---+---+--------------------+---------+
| 2 | 1 | 0 | 0 | (4, 3, 2)          | 3       |
+---+---+---+---+--------------------+---------+
| 3 | 1 | 0 | 1 | (4, 3, 6)          | 4       |
+---+---+---+---+--------------------+---------+
| 4 | 1 | 1 | 1 | (4, 9, 6)          | 6       |
+---+---+---+---+--------------------+---------+
| 5 | 2 | 1 | 1 | (5, 9, 6)          | 5       |
+---+---+---+---+--------------------+---------+
| 6 | 3 | 1 | 1 |                    |         |
+---+---+---+---+--------------------+---------+

n = итерация

На каждом шаге один из трех индексов увеличивается, поэтому алгоритм гарантированно завершится. В худшем случае i, j и k увеличиваются в этом порядке, и алгоритм выполняется за O(n^2) (в данном случае 9). Для данного примера он заканчивается через 5 итераций.

Answer 7

О (п)

Pair find(int[][] indices) {
pair.lBound = max int;
pair.rBound = 0;
index = 0;

for i from 0 to indices.lenght{
    if(pair.lBound > indices[i][0]){
        pair.lBound = indices[i][0]
        index = i;
    }
    if(indices[index].lenght > 0)
        pair.rBound = max(pair.rBound, indices[i][0])
}
remove indices[index][0]

return min(pair, find(indices)}