4

我正在构建一个接收传入短信的应用程序，然后根据关键字，它会查看该关键字是否与它正在运行的任何活动相关联。我现在这样做的方式是加载关键字列表和可能的拼写组合，然后当 SMS 进来时，我会查看所有关键字和组合以查看是否匹配。

不使用这种方法，而是通过实际查找可能与另一个单词匹配的单词，您将如何做到这一点。

假设正确的拼写是 HAMSTER，通常我会给出竞选替代品，如 HMSTER HIMSTER HAMSTAR HAMSTR HAMSTIR 等。

有这样做的聪明方法吗？

仓鼠

“hamstir”.compare_to（“仓鼠”）？匹配

编辑：

2个字怎么样？假设我们知道短信中有两个词需要匹配：

正确的第一个词=第一个词

正确的第二个单词 = AND SECOND WORD

SMS = 第一个字第二个

编辑：

理想情况下，人们应该短信逗号分隔的单词，这样我就会知道在哪里拆分并查找单词。

但是，如果他们不这样做，例如：

唯一关键字 第二参数

我怎么知道单词在哪里分裂？第一个词可能是 3 个词长，第二个词可能是 3 个或 1 个或 2 个等。

在这些示例中，您将如何使用以下技术来找到这两个词？

你会看两次吗？每个需要的参数或关键字一个？

4

5 回答 5

9

最简单的解决方案是使用difflib包，它具有get_close_matches近似字符串匹配的功能：

import difflib
difflib.get_close_matches(word, possibilities)
于 2012-07-19T15:10:08.607 回答
6

您正在寻找的是Levenshtein Distance。

假设您的广告系列列表不是太大，您可以计算输入词与每个广告系列之间的距离，然后选择最短的一个。要过滤掉完全错误的单词，您可能需要设置可接受的最小距离，如果最短距离仍然超出限制，则丢弃输入。

要计算两个单词之间的距离，您可以尝试以下模块之一：

例如，使用levenshtein.py：

from levenshtein import levenshtein
campaigns = (
    "HAMSTER",
    "TWO WORDED",
    "FRIDAY",
)

def get_campaign(word):
  return min(campaigns, key=lambda x: levenshtein(word, x))

用法：

>>> get_campaign("HAMSTA")
'HAMSTER'
>>> get_campaign("HAM WORDED")
'TWO WORDED'
>>> get_campaign("FROODY")
'FRIDAY'
>>> get_campaign("FRIDAY")
'FRIDAY'

请注意，这是一种非常简单的方法，即使输入完全不同，它也总会返回一些东西。

于 2012-07-19T15:06:04.427 回答
2

我使用 levenshtein 距离来解决类似的问题，请参阅http://en.wikipedia.org/wiki/Levenshtein_distance

def distance(u1, u2):
    try:
        s1 = unicode(u1)    
        s2 = unicode(u2)
    except:
        s1 = u1
        s2 = u2        
    if len(s1) < len(s2):
        return distance(u2, u1)
    if not s1:
        return len(s2)

    previous_row = xrange(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
            deletions = current_row[j] + 1       # than s2
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row

    return previous_row[-1]


distance("hamstir", "hamster") < 3
True
distance("god", "hamster") < 3
False
于 2012-07-19T15:06:10.713 回答
1

在我看来，您正在尝试构建拼写检查器。您可以使用最小编辑距离匹配。或者，看看Peter Norvig 的 python 拼写检查器

希望有帮助

于 2012-07-19T15:09:22.037 回答
1

您可以使用模糊匹配和带regex库的命名列表，例如，从列表中查找最多有一个错误（插入、删除、替换）的任何短语：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import regex as re # pip install regex

words = ["first word", "second word", "third"]
sms = u"junk Furst Word second Third"

for m in re.finditer(ur"(?fie)\L<words>{e<=1}", sms, words=words):
    print(m[0]) # the match
    print(m.span()) # return indexes where the match found in the sms
    # to find out which of the words matched:
    print(next(w for w in words
               if re.match(ur"(?fi)(?:%s){e<=1}" % re.escape(w), m[0])))

输出

Furst Word
(5, 14)
first word
Third
(22, 27)
third

或者您可以直接迭代单词：

for w in words:
    for m in re.finditer(ur"(?fie)(?:%s){e<=1}" % re.escape(w), sms):
        print(m[0])
        print(m.span())
        print(w)

它产生与第一个示例相同的输出。

于 2012-07-20T13:32:01.650 回答