3

任务是对由多个单词（aka Multi-Word Expressions）组成的表达式进行分组。

给定 MWE 字典，我需要在检测到 MWE 的输入句子中添加破折号，例如

**Input:** i have got an ace of diamonds in my wet suit .
**Output:** i have got an ace-of-diamonds in my wet-suit .

目前我遍历排序的字典，看看 MWE 是否出现在句子中，并在出现时替换它们。但是有很多浪费的迭代。

有更好的方法吗？一种解决方案是产生所有可能的 n-gram 1st，即chunker2()

import re, time
mwe_list =set([i.strip() for i in codecs.open( \
            "wn-mwe-en.dic","r","utf8").readlines()])

def chunker(sentence):
  for item in mwe_list:
    if item or item.replace("-", " ") in sentence:
      #print item
      mwe_item =  '-'.join(item.split(" "))
      r=re.compile(re.escape(mwe_item).replace('\\-','[- ]'))
      sentence=re.sub(r,mwe_item,sentence)    
  return sentence

def chunker2(sentence):
    nodes = []
    tokens = sentence.split(" ")
    for i in range(0,len(tokens)):
        for j in range(i,len(tokens)):
            nodes.append(" ".join(tokens[i:j]))
    n = sorted(set([i for i in nodes if not "" and len(i.split(" ")) > 1]))

    intersect = mwe_list.intersection(n)

    for i in intersect:
        print i
        sentence = sentence.replace(i, i.replace(" ", "-"))

    return sentence

s = "i have got an ace of diamonds in my wet suit ."

time.clock()
print chunker(s)
print time.clock()

time.clock()
print chunker2(s)
print time.clock()
4

2 回答 2

2

我会尝试这样做：

  • 对于每个句子，构建一组 n-gram，直到给定长度（列表中最长的 MWE）。
  • 现在，只需执行mwe_nmgrams.intersection(sentence_ngrams)并搜索/替换它们。

您不必通过迭代原始集合中的所有项目来浪费时间。

这是一个稍微快一点的版本chunker2：

def chunker3(sentence):
    tokens = sentence.split(' ')
    len_tokens = len(tokens)
    nodes = set()

    for i in xrange(0, len_tokens):
        for j in xrange(i, len_tokens):
            chunks = tokens[i:j]

            if len(chunks) > 1:
                nodes.add(' '.join(chunks))

    intersect = mwe_list.intersection(n)

    for i in intersect:
        print i
        sentence = sentence.replace(i, i.replace(' ', '-'))

    return sentence
于 2013-01-22T05:47:31.247 回答
2

首先，2 倍的改进：因为您将 MWE 替换为带连字符的版本，所以您可以预处理字典 (wn-mwe-en.dic) 以消除集合中 MWE 中的所有连字符，从而消除一个字符串比较。如果您允许在句子中使用连字符，那么您还必须对其进行预处理，大概是在线处理，以收取小罚。这应该将您的运行时间减半。

接下来，一个小的改进：不可变元组通常比集合或列表更快地迭代（它们是可变的，迭代器必须在每一步检查内存中元素的移动）。如您所愿， set() 转换将消除重复项。元组位将在内存中固定它，允许 python 解释器及其编译的库进行低级迭代优化。

最后，在进行所有比较之前，您可能应该将句子和 MWE 解析为单词或标记，这将减少单词平均长度所需的字符串比较数（如果您的单词长度为 4 个字符，则为 4x平均的）。您还可以嵌套另一个循环来搜索 MWE 中的第一个单词作为共享该第一个单词的所有 MWE 的锚点，从而减少所需的字符串比较的长度。但我会把这个最大的份额留给你对真实数据进行实验。并且根据解释器与编译库的效率，在 python 级别执行所有这些拆分嵌套循环实际上可能会减慢速度。

所以这是前两个简单的“确定”赌注的结果。尽管进行了预处理，但应该快 2 倍，除非你的句子很短。

mwe_list = set(i.strip() for i in codecs.open("wn-mwe-en.dic", "r", "utf8").readlines())
mwe_list = tuple(mwe.replace('-', ' ').strip() for mwe in mwe_list)
sentence = sentence.replace('-', ' ').strip()

def chunker(sentence):
  for item in mwe_list:
    if item in sentence:
    ...

Couldn't find a .dic file on my system or I'd profile it for you.

于 2013-01-22T06:25:20.863 回答