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

Question

В чем сложность алгоритма, который используется для поиска наименьшего фрагмента, содержащего все ключевые слова поиска?

Answer 1

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

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

Таким образом, в основном текущий блок представляет собой последовательность FIFO: новые слова поступают в правый конец и удаляются в процессе нормализации из левого конца.

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

Например, рассмотрим текст

CxxxAxxxBxxAxxCxBAxxxC

с ключевыми словами A, B и C. Просматривая текст, вы построите следующую последовательность блоков

C
CA
CAB - all words, length 9 (CxxxAxxxB...)
CABA - all words, length 12 (CxxxAxxxBxxA...)
CABAC - violates The Property, remove first C
ABAC - violates The Property, remove first A
BAC - all words, length 7 (...BxxAxxC...)
BACB - violates The Property, remove first B
ACB - all words, length 6 (...AxxCxB...)
ACBA - violates The Property, remove first A
CBA - all words, length 4 (...CxBA...)
CBAC - violates The Property, remove first C
BAC - all words, length 6 (...BAxxxC)

Лучший построенный нами блок имеет длину 4, что в данном случае является ответом

CxxxAxxxBxxAxx CxBA xxxC

Точная сложность этого алгоритма зависит от входных данных, так как он диктует, сколько итераций сделает процесс нормализации, но без учета нормализации сложность будет тривиально равна O(N * log M), где N - это количество слов в text, M - количество ключевых слов, а O(log M) - сложность проверки, принадлежит ли текущее слово к набору ключевых слов.

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

Answer 2

Я думаю, что решение, предложенное AndreyT, предполагает отсутствие дубликатов в ключевых словах / поисковых терминах. Кроме того, текущий блок может стать таким же большим, как и сам текст, если текст содержит много повторяющихся ключевых слов. Например: Текст: 'ABBBBBBBBBB' Текст ключевого слова: «AB» Текущий блок: 'ABBBBBBBBBB'

Во всяком случае, я реализовал в C #, провел базовое тестирование, было бы неплохо получить некоторые отзывы о том, работает ли он или нет:

    static string FindMinWindow(string text, string searchTerms)
    {
        Dictionary<char, bool> searchIndex = new Dictionary<char, bool>();
        foreach (var item in searchTerms)
        {
            searchIndex.Add(item, false);
        }

        Queue<Tuple<char, int>> currentBlock = new Queue<Tuple<char, int>>();
        int noOfMatches = 0;
        int minLength = Int32.MaxValue;
        int startIndex = 0;
        for(int i = 0; i < text.Length; i++)
        {
            char item = text[i];
            if (searchIndex.ContainsKey(item))
            {
                if (!searchIndex[item])
                {
                    noOfMatches++;
                }

                searchIndex[item] = true;
                var newEntry = new Tuple<char, int> ( item, i );
                currentBlock.Enqueue(newEntry);

                // Normalization step.
                while (currentBlock.Count(o => o.Item1.Equals(currentBlock.First().Item1)) > 1)
                {
                    currentBlock.Dequeue();
                }

                // Figuring out minimum length.
                if (noOfMatches == searchTerms.Length)
                {
                    var length = currentBlock.Last().Item2 - currentBlock.First().Item2 + 1;
                    if (length < minLength)
                    {
                        startIndex = currentBlock.First().Item2;
                        minLength = length;
                    }
                }
            }
        }
        return noOfMatches == searchTerms.Length ? text.Substring(startIndex, minLength) : String.Empty;
    }

Answer 3

Вот решение с использованием Java 8.

static Map.Entry<Integer, Integer> documentSearch(Collection<String> document, Collection<String> query) {
    Queue<KeywordIndexPair> queue = new ArrayDeque<>(query.size());
    HashSet<String> words = new HashSet<>();

    query.stream()
        .forEach(words::add);

    AtomicInteger idx = new AtomicInteger();
    IndexPair interval = new IndexPair(0, Integer.MAX_VALUE);
    AtomicInteger size = new AtomicInteger();
    document.stream()
        .map(w -> new KeywordIndexPair(w, idx.getAndIncrement()))
        .filter(pair -> words.contains(pair.word)) // Queue.contains is O(n) so we trade space for efficiency
        .forEach(pair -> {
            // only the first and last elements are useful to the algorithm, so we don't bother removing
            // an element from any other index. note that removing an element using equality
            // from an ArrayDeque is O(n)
            KeywordIndexPair first = queue.peek();
            if (pair.equals(first)) {
                queue.remove();
            }
            queue.add(pair);
            first = queue.peek();
            int diff = pair.index - first.index;
            if (size.incrementAndGet() == words.size() && diff < interval.interval()) {
                interval.begin = first.index;
                interval.end = pair.index;
                size.set(0);
            }
        });

    return new AbstractMap.SimpleImmutableEntry<>(interval.begin, interval.end);
}

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

Тест:

Документ : яблоко, банан, яблоко, яблоко, собака, кошка, яблоко, собака, банан, яблоко, кот, собака

Запрос : банан, кошка

Интервал : 8, 10

Answer 4

Это интересный вопрос.Чтобы переформулировать это более формально: учитывая список L (веб-страницу) длины n и набор S (запрос) размера k, найдите наименьший подсписок L, который содержит все элементы S.

Я начну с решения «грубой силы» в надежде вдохновить других на его решение.Обратите внимание, что членство в наборе может быть сделано в постоянное время, после одного прохода через набор.См. этот вопрос .Также обратите внимание, что это предполагает, что все элементы S фактически находятся в L, в противном случае он просто вернет подсписок от 1 до n.

best = (1,n)
For i from 1 to n-k:  
  Create/reset a hash found[] mapping each element of S to False.
  For j from i to n or until counter == k:  
    If found[L[j]] then counter++ and let found[L[j]] = True;
  If j-i < best[2]-best[1] then let best = (i,j).

Сложность по времени равна O ((n + k) (nk)).То есть n ^ 2-иш.