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

Ответ 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 - количество слов в текст и M - это количество ключевых слов, а O(log M) - сложность проверки того, принадлежит ли текущее слово к набору ключевых слов.

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

Ответ 2

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

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

    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;
    }

Ответ 3

Это интересный вопрос. Чтобы повторить его более формально: Учитывая список 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) (n-k)). Ie, n ^ 2-ish.

Ответ 4

Я тестировал решение AnT широко. Единственная проблема с этим решением заключается в том, что он рассматривает дубликаты только тогда, когда они появляются перед фрагментом. Ярким примером является следующее: text = x4x2xx88x4248 key = 4 2 8 алгоритм AnT не сможет найти случай 248. Чтобы исправить это, вам нужно только изменить указанное свойство: Каждое ключевое слово должно присутствовать в текущем блоке только один раз. Поэтому каждый раз, когда вы добавляете новый ключ в блок, удалите предыдущее вхождение того же ключа.