Найти все permitation для списка или списка слов в очень длинном тексте

Question

Учитывая список слов = {w1, w2, w3, w1, w2}

Найти все перестановки выше список слов в длинном тексте.

длинный текстовый список = {Это длинный текст w1 w2 w3 w4 и w1 w2 w1 w2 w3. Это еще один длинный текст, который не имеет перестановку, поскольку он не содержит все слова w1, w2, w2, w2, w2, но это перестановка w2 w2 w3 w1 w1} разделены пробелом

Что является наиболее эффективным Алгоритм решения этой проблемы?

Я думал, что для каждого уникального слова в списке сначала присваивается кортеж (уникальный #, единственный простой #) {w1 = [101, 5], w2 = [103, 7], w3 = [205, 11] } и вычислить сумму для всего списка с помощью назначенных кортежей: w1 [101 * 5] + w2 [103 * 7] + w3 [205 * 11] + w1 [101 * 5] + + w2 [103 * 7] = 4707

Вот pudo-код:

targetSum = 4707; 
long sum = 0; 
for (int i = 0; i < Text.size(); i++){ 
    look up (unique #, unique prime #) 
    sum + = ((unique # * unique prime) ; 
    if( i > list.size()){ 
     sum = sum – (look up (unique #, unique prime # for index 
       (i – list.size()) and subtract tuple sum) 
    } 

    if(targetSum = = sum){ 
     // this is possible match so hashMap lookup verify again that this reagion is actual match. 
} 

}

есть ли логика лучше или алгоритм для этого?

Update:

Я читал дальше шаблон согласования Z-алгоритма (Z-Boxes), но я не могу видеть, как Z-боксы или Z-массив будет сделать его лучше, если все перестановки не знать заранее. Не уверен, есть ли лучший способ?

Спасибо всем, кто делится знаниями.

Спасибо,

Bhavesh

Answer 1

Если слова должны быть смежными, а затем начать строить словарь слов, которые вы ищете, наряду с их подсчетами. Для вашего примера [w1, w2, w3, w1, w2], словарь будет содержать:

{w1, 2} 
{w2, 2} 
{w3, 1} 

вызовов, что входящий словарь.

Также создайте пустой словарь того же типа (т. Е. Слово, счет). Вызовите этот исходный словарь.

Затем создайте очередь, размер которой зависит от количества слов, которые вы ищете. Очередь изначально пуста.

Затем вы начинаете движение через текст, слово за словом, как это сделать:

for each text_word in text 
    if queue.count == number of words 
     queue_word = remove word from queue 
     if queue_word is in outgoing dictionary 
      remove from outgoing 
      add to incoming 
     end if 
    end if 

    add text_word to queue 
    if text_word is in incoming dictionary 
     remove text_word from incoming dictionary 
     add text_word to outgoing dictionary 
     if incoming dictionary is empty 
      you found a permutation 
     end if 
    end if 

Единственная сложность здесь в том, что «добавить слово в словарь» и «удалить слово в словарь» должны принимать во учет возможности множественных вхождений одного и того же слова. Таким образом, ваше удаление - это действительно что-то вроде:

count = dictionary[word].Count = 1 
if (count == 0) 
    dictionary.Remove(word) 
else 
    dictionary[word].Count = count 

И добавление похоже.

Answer 2

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

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

def permindex(text, pattern, start = 0): 
    """Index of first permutation of the pattern in text""" 

    if len(text) - start < len(pattern): 
     return -1 

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

    value = {} 
    goal = 1 
    for p in pattern: 
     if not p in value: 
      value[p] = primes.pop(0) 

     goal *= value[p] 

    prod = 1 
    for t in text[start:start + len(pattern)]: 
     prod *= value.get(t, 1) 

    i = start 

    for j in range(start + len(pattern), len(text)): 

     if goal == prod: 
      return i 

     prod /= value.get(text[i], 1) 
     prod *= value.get(text[j], 1) 

     i += 1 

    if goal == prod: 
     return len(text) - len(pattern) 

    return -1 

Применяя это к вашей проблеме:

import re 

patt = "w1 w2 w3 w1 w2".split() 

text = re.split("\W+", 
     """This is long text w1 w2 w3 w4 and w1 w2 w1 w2 w3. This 
     yet another long text which does not have permutation because 
     it does not contain all words w1,w2,w2,w2,w2 , but this is 
     permutation w2 w2 w3 w1 w1""") 

p = permindex(text, patt) 
while p >= 0: 
    print p, text[p: p + len(patt)] 
    p = permindex(text, patt, p + 1) 

выходы:

9 ['w1', 'w2', 'w1', 'w2', 'w3'] 
40 ['w2', 'w2', 'w3', 'w1', 'w1']