Python URL 字符串匹配

Question

我的问题是这样的。我有一个很长的URL列表，比如：

www.foo.com/davidbobmike1joe
www.foo.com/mikejoe2bobkarl
www.foo.com/joemikebob
www.foo.com/bobjoe

我需要把这个列表里的所有网址进行比较，提取出这些网址子域名中的关键词（在这个例子中是：david、joe、bob、mike、karl），然后按出现的频率进行排序。我查阅了一些库，比如nltk。但是这里的问题是，网址中没有空格，无法独立地分割每个词。你有什么建议可以帮我解决这个问题吗？

Answer 1

概述

你可以用这段代码来提取名字，只需要传入一个名字列表，比如 [david, bob, 等等]：

有没有简单的方法可以从没有空格的句子中生成一个可能的单词列表？

然后可以使用 collections.Counter 来计算每个名字出现的频率。

代码

from Bio import trie
import string
from collections import Counter


def get_trie(words):
    tr = trie.trie()
    for word in words:
        tr[word] = len(word)
    return tr

def get_trie_word(tr, s):
    for end in reversed(range(len(s))):
        word = s[:end + 1]
        if tr.has_key(word): 
            return word, s[end + 1: ]
    return None, s

def get_trie_words(s):
    names = ['david', 'bob', 'karl', 'joe', 'mike']
    tr = get_trie(names)
    while s:
        word, s = get_trie_word(tr, s)
        yield word

def main(urls):
    d = Counter()
    for url in urls:
        url = "".join(a for a in url if a in string.lowercase)
        for word in get_trie_words(url):
            d[word] += 1
    return d

if __name__ == '__main__':
    urls = [
        "davidbobmike1joe",
        "mikejoe2bobkarl",
        "joemikebob",
        "bobjoe",
    ]
    print main(urls)

结果

Counter({'bob': 4, 'joe': 4, 'mike': 3, 'karl': 1, 'david': 1})

Answer 2

限制

如果你不使用字典，那么你的算法就会需要很多计算。更重要的是，无法区分只出现一次的关键词（比如：“karl”）和一些无意义的字符串（比如：“e2bo”）。我的解决方案只能尽量做到，只有当你的网址列表中包含多个重复的关键词时，它才会有效。

基本思路

我假设一个词是由至少三个字符组成的频繁出现的字符序列。这样可以避免字母“o”成为最常见的词。

基本思路如下：

• 统计所有n个字母的序列，并选择那些出现多次的。
• 去掉那些是更大序列一部分的序列。
• 按受欢迎程度排序，这样你就能得到一个接近解决你问题的方案。（这部分留给读者自己练习）

代码示例

import operator

sentences = ["davidbobmike1joe" , "mikejoe2bobkarl", "joemikebob", "bobjoe", "bobbyisawesome", "david", "bobbyjoe"];
dict = {}

def countWords(n):
    """Count all possible character sequences/words of length n occuring in all given sentences"""
    for sentence in sentences:
        countWordsSentence(sentence, n);

def countWordsSentence(sentence, n):
    """Count all possible character sequence/words of length n occuring in a sentence"""
    for i in range(0,len(sentence)-n+1):
        word = sentence[i:i+n]
        if word not in dict:
            dict[word] = 1;
        else:
            dict[word] = dict[word] +1;

def cropDictionary():
    """Removes all words that occur only once."""
    for key in dict.keys():
        if(dict[key]==1):
            dict.pop(key);

def removePartials(word):
    """Removes all the partial occurences of a given word from the dictionary."""
    for i in range(3,len(word)):
        for j in range(0,len(word)-i+1):
            for key in dict.keys():
               if key==word[j:j+i] and dict[key]==dict[word]:
                   dict.pop(key);

def removeAllPartials():
    """Removes all partial words in the dictionary"""
    for word in dict.keys():
        removePartials(word);

for i in range(3,max(map(lambda x: len(x), sentences))):
    countWords(i);
    cropDictionary();
    removeAllPartials();

print dict;

输出结果

>>> print dict;
{'mike': 3, 'bobby': 2, 'david': 2, 'joe': 5, 'bob': 6}

给读者的一些挑战

• 在打印字典之前，按值对字典进行排序。（如何按值排序Python字典）
• 在这个例子中，“bob”出现了六次，其中两次是“bobby”的部分词。判断这是否有问题，并在必要时修复。
• 考虑字母的大小写。