python - vanilla python - (抄袭检查器)如何检测原始句子中相同的单词？

Question

我想用 vanilla python 制作一个简单的抄袭检查器。在 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']

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

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] 以避免重新检查 B 中的所有索引A 的每个单词:

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|*|A 的单词在 B|*最长匹配中的最大出现次数)。您还可以在 len(A)-4 而不是 len(A)-1 处停止迭代。

如果您想检查大量文档是否存在抄袭，这可能仍然太慢。