Python文本搜索问题

Question

我想知道，如果你在Python中打开一个文本文件。然后你想搜索包含许多字母的单词。

假设您输入6个不同的字母（a，b，c，d，e，f）要搜索。 你想找到匹配至少3个字母的单词。 每个字母只能出现一次。 而且字母'a'必须包含。

对于这种特定类型的搜索，代码应该如何？

Answer 1

这里，如果我不得不写这个，我会做什么：

我不得不说，给定一个字，会检查它是否满足条件，并会返回一个布尔标志的功能。

然后，我会有一些代码可以遍历文件中的所有单词，将它们呈现给函数，并将函数返回的那些代码打印出来True。

Answer 2

让我们来看看...

return [x for x in document.split() 
     if 'a' in x and sum((1 if y in 'abcdef' else 0 for y in x)) >= 3] 

split不带参数作为一个“字”的功能，对分割不包含字符的任意空白和去除的话。然后你检查字母“a”是否在单词中。如果单词中包含“a”，则使用生成器表达式覆盖单词中的每个字母。如果该字母在可用字母串的内部，则它返回一个1，这对总和有贡献。否则，它返回0.然后，如果和为3或更大，它会保留它。使用生成器而不是列表理解，因为sum将接受任何可迭代的东西，并且它会停止创建临时列表（减少内存开销）。

由于使用in（它在字符串上应该有一个O（n）时间），所以它没有最佳访问时间，但这通常不是一个非常大的问题，除非数据集很大。您可以优化一下将字符串打包成一个集合，并且常量'abcdef'可以很容易地成为一个集合。我只是不想毁掉漂亮的单线。

编辑：哦，并且为了改善if部分（这是效率低下的地方）的时间，你可以将它分离成一个迭代字符串一次的函数，如果条件满足则返回True。我会这样做，但它毁了我的一班。

编辑2：我没有看到“必须有3个不同的字符”部分。你不能在一个班轮中做到这一点。你可以把if部分放到一个函数中。

def is_valid(word, chars): 
    count = 0 
    for x in word: 
     if x in chars: 
      count += 1 
      chars.remove(x) 
    return count >= 3 and 'a' not in chars 

def parse_document(document): 
    return [x for x in document.split() if is_valid(x, set('abcdef'))] 

这一次应该不会对现实世界的数据集的任何性能问题。

Answer 3

words = 'fubar cadre obsequious xray' 

def find_words(src, required=[], letters=[], min_match=3): 
    required = set(required) 
    letters = set(letters) 

    words = ((word, set(word)) for word in src.split()) 
    words = (word for word in words if word[1].issuperset(required)) 
    words = (word for word in words if len(word[1].intersection(letters)) >= min_match) 
    words = (word[0] for word in words) 
    return words 

w = find_words(words, required=['a'], letters=['a', 'b', 'c', 'd', 'e', 'f']) 
print list(w) 

编辑1：我也没看过的要求不够紧密。确保一个单词只包含一个有效字母的实例。

from collections import Counter 

def valid(word, letters, min_match): 
    """At least min_match, no more than one of any letter""" 
    c = 0 
    count = Counter(word) 
    for letter in letters: 
     char_count = count.get(letter, 0) 
     if char_count > 1: 
      return False 
     elif char_count == 1: 
      c += 1 
     if c == min_match: 
      return True 
    return True 


def find_words(srcfile, required=[], letters=[], min_match=3): 
    required = set(required) 
    words = (word for word in srcfile.split()) 
    words = (word for word in words if set(word).issuperset(required)) 
    words = (word for word in words if valid(word, letters, min_match)) 
    return words 

Answer 4

我同意AIX的总体规划，但它或许更普遍比“设计模式”，而我不知道它能走多远你，因为它归结为，“想出一个办法检查你想查找的内容，然后检查你需要检查的所有内容。“

关于如何找到你想找到的建议：你已经进入了算法研究的一个最基本的领域，尽管LCS（最长公共子串）被覆盖得更好，但你找到好东西没有问题。为遏制例子要么这个话题我见过的最严格的讨论是在谷歌CS书呆子的网站：http://neil.fraser.name他一些所谓的差异匹配，补丁，它被释放，并在许多不同的语言，包括Python优化，从而可以在这里下载： http://code.google.com/p/google-diff-match-patch/

如果您想了解更多关于Python和算法，马格努斯赫特兰已经撰写了有关蟒蛇算法伟大的书和他的网站上有串中的一些例子匹配和模糊字符串匹配等等，包括levenshtein距离在内的一种非常简单的抓取格式。 （谷歌为magnus hetland，我不记得地址）。

内你可以看看difflib，它提供了许多方法来评估字符串的相似性的标准库。你正在寻找不同的遏制，但它是非常相关的，你可能会根据你的需要制作一套你可以比较的候选单词。

另外，您可以使用新的除了蟒蛇，计数器，并重建你要测试的字符串表中的单词，然后让需要的1个或多个计数为每个测试信件的功能。

最后，到AIX的方法的第二部分“然后将其应用到要测试一切，”我建议你看一下itertools。如果您有什么样的效率约束，你将要使用的发电机和测试像一个AIX建议可以最有效地在Python与itertools.ifilter进行。你有你的函数，你要保留值，并且内置函数布尔返回True。所以你可以做itertools.ifilter（bool，test_iterable），它会返回所有成功的值。

好运