Как найти все самые длинные общие подстроки, которые существуют в нескольких документах? - PullRequest
Новая
       23

Как найти все самые длинные общие подстроки, которые существуют в нескольких документах?

1 голос
/ 06 февраля 2020

У меня есть много текстовых документов, которые я хочу сравнить друг с другом и удалить весь текст, который между ними совпадает. Это делается для того, чтобы удалить согласованный текст на панели котлов, чтобы его можно было удалить для НЛП.

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

Вот пример того, что я пытаюсь выполнить sh:

DocA: 

Title: To Kill a Mocking Bird
Author: Harper Lee
Published: July 11, 1960

DocB: 

Title: 1984
Author: George Orwell
Published: June 1949

Do cC: 

Title: The Great Gatsby
Author: F. Scott Fitzgerald

Вывод будет отображать что-то вроде: 

{
    'Title': 3,
    'Author': 3,
    'Published': 2,
}

Результаты затем будут использоваться для удаления общих черт между документы.

Вот код, который я протестировал в python. Это невероятно при любом значительном количестве перестановок: 

file_perms = list(itertools.permutations(files, 2))
results = {}
for p in file_perms:
    doc_a = p[0]
    doc_b = p[1]

    while True:
        seq_match = SequenceMatcher(a=doc_a, b=doc_b)
        match = seq_match.find_longest_match(0, len(doc_a), 0, len(doc_b)) 

        if (match.size >= 5): 
            doc_a_start, doc_a_stop = match.a, match.a + match.size
            doc_b_start, doc_b_stop = match.b, match.b + match.size 
            match_word = doc_a[doc_a_start:doc_a_stop]

            if match_word in results:
                results[match_word] += 1
            else:
                results[match_word] = 1

            doc_a = doc_a[:doc_a_start] + doc_a[doc_a_stop:]
            doc_b = doc_b[:doc_b_start] + doc_b[doc_b_stop:]
        else: 
            break 

df = pd.DataFrame(
    {
        'Value': [x for x in results.keys()],
        'Count': [x for x in results.values()]
    }
)
print(df)

1 Ответ

1 голос
/ 06 февраля 2020

создайте набор из каждого документа, создайте счетчик для каждого слова, сколько раз оно появляется, повторяется по каждому документу, когда вы найдете слово, которое появляется в 70% -90% документов, добавьте его и слово после него как кортеж к новому счетчику и снова .. 

 from collections import Counter

 one_word = Counter()
 for doc in docs:
     word_list = docs.split(" ")
     word_set = set(word_list)
     for word in word_set:
         one_word[word]+=1

 two_word = Counter()
 threshold = len(docs)*0.7

 for doc in docs:
     word_list = doc.split(" ")
     for i in range(len(word_list)-1):
         if one_word[word_list[i]]>threshold:
             key = (word_list[i], word_list[i+1])

вы можете играть с порогом и продолжать до тех пор, пока счетчик не пуст

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

from collections import Counter
import os
import glob
TR =1 #threshold
dir = r"D:\docs"
path = os.path.join(dir,"*.txt")
files = glob.glob(path)
one_word = {}
all_docs = {}
for file in files:
    one_word[file] = set()
    all_docs[file] = []
    with open(file) as doc:
        for row in doc:
            for word in row.split():
                one_word[file].add(word)
                all_docs[file].append(word)
#now one_word is a dict where the kay is file name and the value is set of words in it
#all_docs is a dict file name is the key and the value is the complete doc stord in a list word by word
common_Frase = Counter()
for key in one_word:
    for word in one_word[key]:
        common_Frase[word]+=1
#common_Frase containe a count of all words appearence in all files (every file can add a word once)

two_word = {}
for key in all_docs:
    two_word[key] = set()
    doc = all_docs[key]
    for index in range(len(doc)-1):
        if common_Frase[doc[index]]>TR:
            val = (doc[index], doc[index+1])
            two_word[key].add(val)

for key in two_word:
    for word in two_word[key]:
        common_Frase[word]+=1
#now common_Frase contain a count of all two words frase

three_word = {}
for key in all_docs:
    three_word[key] = set()
    doc = all_docs[key]
    for index in range(len(doc)-2):
        val2 = (doc[index], doc[index+1])
        if common_Frase[val2]>TR:
            val3 = (doc[index], doc[index+1], doc[index+2])
            three_word[key].add(val3)


for key in three_word:
    for word in three_word[key]:
        common_Frase[word]+=1

for k in common_Frase:
    if common_Frase[k]>1:
        print(k)

это выход

когда, как и все, Не один И мой слух и чувство Тогда ты из Я во мне, Ты далеко, Я никогда не буду тем, что когда-либо существовало там, Из-за внизу. Слова, которые были («все», «the») («И», «the») («the», «words»). ) ('By', 'the') ('and', 'the') ('in', 'the')

...