在字符串中查找匹配的短语和单词python

Question

使用python，从给定的字符串中提取常用短语或单词的最有效方法是什么？

例如，

string1="once upon a time there was a very large giant called Jack" 
string2="a very long time ago was a very brave young man called Jack" 

将返回：

["a","time","there","was a very","called Jack"] 

一个会如何在有效地这样做（在我来说，我需要做的这几千年1000字的文件） ？

Answer 1

你可以每个字符串split，然后intersectset s。

string1="once upon a time there was a very large giant called Jack" 
string2="a very long time ago was a very brave young man called Jack" 
set(string1.split()).intersection(set(string2.split())) 

结果

set(['a', 'very', 'Jack', 'time', 'was', 'called']) 

注意这仅匹配单个的单词。你必须更具体地说明你会认为什么是“短语”。最长的连续匹配子字符串？这可能会变得更加复杂。

Answer 2

在自然语言处理中，通常使用n-grams从句子中提取常见模式和序列。 在Python中，你可以使用优秀的NLTK模块。

要计算和查找最常见的，可以使用collections.Counter。

下面是2-克例如：

from nltk.util import ngrams 
from collections import Counter 
from itertools import chain 

string1="once upon a time there was a very large giant called Jack" 
string2="a very long time ago was a very brave young man called Jack" 

n = 2 
ngrams1= ngrams(string1.split(" "), n) 
ngrams2= ngrams(string2.split(" "), n) 

counter= Counter(chain(ngrams1,ngrams2))  #count occurrences of each n-gram 
print [k[0] for k,v in counter.items() if v>1] #print all ngrams that come up more than once 

输出：

[('called', 'Jack'), ('was', 'a'), ('a', 'very')] 

输出与n=3：

[('was', 'a', 'very')] 

输出与n=1（无元组）：

['Jack', 'a', 'was', 'time', 'called', 'very'] 

Answer 3

这是一个经典的动态规划问题。所有你需要做的是为string1建立一个后缀树，用单词而不是字母（这是通常的表述）。这是一个illustrative example of a suffix tree。

1. 将树中的所有节点标记为s1。
2. 逐个插入所有后缀string2。
3. 步骤2中后缀所经过的所有节点标记为s2。
4. 在步骤2中创建的任何新节点也标记为s2。
5. 在最终的树中，标记为s1和s2的每个节点的路径标签是常见的子字符串。

该算法在this lecture note中简洁地解释。

对于长度n和m的两个字符串，后缀树建设需要O(max(n,m))，和所有匹配的子串（在你的情况，词或短语）可以在O(#matches)进行搜索。