香草蟒蛇-(抄袭检查器)如何检测在原始句子中相同的单词？

Question

我想用香草蟒蛇做一个简单的抄袭检查器。而不使用python中的外部库

因此，如果相同的单词连续出现超过4次，我希望打印输出(连续的相同单词)

我尝试了下面的代码。但它会显示每个相同的单词，即使这些单词连续相同的次数不到4次。

b1='i guess that osaka city is just a souless city it is obviously weird'.split(' ')
a1='all of the meaning less time i guess thinking that osaka city is huge a souless city it is obviously weird'.split(' ')

# expected_result
#['that osaka city is','a souless city it is obviously weird']



temp1=[]
for b in b1:
    for a in a1:
        if b == a :
            temp1.append(b)

        if len(temp1)>=4:
            print(' '.join(temp1))
        else:
            print('==')

然而，结果是

i guess that osaka city city is is a souless city city it is is obviousl
y
i guess that osaka city city is is a souless city city it is is obviousl
y
i guess that osaka city city is is a souless city city it is is obviousl
y weird

还有..。这就是我想做的

#### Example; 

# INPUT
a = 'Hello my name is Osaka, today I learned about Mochi
is just a shit of snowman'
b = 'Hello my name is Kidney, bullshit, mann yesterday I learned about Katzu is just a shit of snowman'
# EXPECTED OUTPUT
['Hello my name is','is just a shit of snowman']

Answer 1

将a1中的每个单词与b1中的每个单词进行比较。所有匹配的单词都会添加到temp1中。但是你从来没有检查过单词的序列。这就是为什么你会得到b1中所有的a1单词。

这里有一个比较序列的简单方法:取a1和b1中的每两个索引，并尝试在字符匹配时前进。如果找到4个或更多匹配字符，则输出字符：

B='i guess that osaka city is just a souless city it is obviously weird'.split(' ')
A='all of the meaning less time i guess thinking that osaka city is huge a souless city it is obviously weird'.split(' ')

for i in range(len(A)):
    for j in range(len(B)):
        m, n = i, j
        while m<len(A) and n<len(B) and A[m] == B[n]:
            m, n = m+1, n+1
        if m-i >= 4:
            print((i, j), A[i:m])

如果你在"Vanilla Python“中使用itertools (我知道VanillaJS，但我不确定"Vanilla Python”是什么意思)，你可以这样写：

import itertools
for i, j in itertools.product(range(len(A)), range(len(B))):
    L = [u for u,v in itertools.takewhile(lambda u_v : u_v[0]==u_v[1], zip(A[i:], B[j:]))]
    if len(L)>=4:
        print((i,j), L)

输出

(9, 2) ['that', 'osaka', 'city', 'is']
(14, 7) ['a', 'souless', 'city', 'it', 'is', 'obviously', 'weird']
(15, 8) ['souless', 'city', 'it', 'is', 'obviously', 'weird']
(16, 9) ['city', 'it', 'is', 'obviously', 'weird']
(17, 10) ['it', 'is', 'obviously', 'weird']

你会得到一些垃圾，因为如果['a', 'souless', 'city', 'it', 'is', 'obviously', 'weird']是从(14, 7)开始的最长匹配，我们知道从(15, 8)开始的列表也将是一个匹配。让我们添加一个exclude集来删除这些子列表：

exclude = set()
for i in range(len(A)):
    for j in range(len(B)):
        if (i,j) in exclude:
            exclude.remove((i,j))
            continue
        m, n = i, j
        while m<len(A) and n<len(B) and A[m] == B[n]:
            m, n = m+1, n+1
        if m-i >= 4:
            print((i, j), A[i:m])
            exclude.update((i+k, j+k) for k in range(1, m-i))
            print ("exclude = ", exclude)

输出：

(9, 2) ['that', 'osaka', 'city', 'is']
exclude =  {(12, 5), (11, 4), (10, 3)}
(14, 7) ['a', 'souless', 'city', 'it', 'is', 'obviously', 'weird']
exclude =  {(20, 13), (16, 9), (17, 10), (15, 8), (19, 12), (18, 11)}

这种方法有效，但非常慢:时间复杂度为O(|A|*|B|*最长匹配)。可以使用以下方法省去一些检查:为列表|B|构建字典word -> [positions]，以避免为A的每个单词重新检查B中的所有索引

positions_by_word_in_B = {}
for j, word in enumerate(B):
    positions_by_word_in_B.setdefault(word, []).append(j)

输出：

{'i': [0], 'guess': [1], 'that': [2], 'osaka': [3], 'city': [4, 9], 'is': [5, 11], 'just': [6], 'a': [7], 'souless': [8], 'it': [10], 'obviously': [12], 'weird'
: [13]}

主循环变成：

for i in range(len(A)):
    for j in positions_by_word_in_B.get(A[i], []):
        # all positions of A[i] in B, maybe none

时间复杂度为O(|B| +|A|*|B中A的单词最大出现次数|*最长匹配)。您还可以在len(A)-4而不是len(A)-1处停止迭代。

如果你想检查大量文档的抄袭行为，这可能还是太慢了。