14

我正在尝试开发一个 python 算法来检查一个字符串是否可以是另一个单词的缩写。例如

  • fck是匹配的，fc kopenhavn因为它匹配单词的第一个字符。fhk不匹配。
  • fco不应该匹配fc kopenhavn，因为没有人会将 FC Kopenhavn 缩写为 FCO。
  • irl是匹配的in real life。
  • ifk是匹配的ifk goteborg。
  • aik是匹配的allmanna idrottskluben。
  • aid是匹配的allmanna idrottsklubben。这不是真正的团队名称缩写，但我想很难排除它，除非您应用有关瑞典缩写如何形成的领域特定知识。
  • manu是匹配的manchester united。

很难描述算法的确切规则，但我希望我的例子能说明我所追求的。

更新我在显示匹配字母大写的字符串时犯了一个错误。在实际场景中，所有字母都是小写的，所以并不像检查哪些字母是大写那么简单。

4

5 回答 5

14

这通过了所有测试，包括我创建的一些额外测试。它使用递归。以下是我使用的规则：

  • 缩写的第一个字母必须与正文的第一个字母匹配

  • 缩写的其余部分（缩写减去第一个字母）必须是以下缩写：

    • 剩余的单词，或
    • 从第一个单词的任何位置开始的剩余文本 。
tests=(
    ('fck','fc kopenhavn',True),
    ('fco','fc kopenhavn',False),
    ('irl','in real life',True),
    ('irnl','in real life',False),    
    ('ifk','ifk gotebork',True),   
    ('ifko','ifk gotebork',False),    
    ('aik','allmanna idrottskluben',True),
    ('aid','allmanna idrottskluben',True),
    ('manu','manchester united',True), 
    ('fz','faz zoo',True), 
    ('fzz','faz zoo',True),
    ('fzzz','faz zoo',False),    
    )

def is_abbrev(abbrev, text):
    abbrev=abbrev.lower()
    text=text.lower()
    words=text.split()
    if not abbrev:
        return True
    if abbrev and not text:
        return False
    if abbrev[0]!=text[0]:
        return False
    else:
        return (is_abbrev(abbrev[1:],' '.join(words[1:])) or
                any(is_abbrev(abbrev[1:],text[i+1:])
                    for i in range(len(words[0]))))

for abbrev,text,answer in tests:
    result=is_abbrev(abbrev,text)
    print(abbrev,text,result,answer)
    assert result==answer
于 2011-09-07T09:28:07.337 回答
4

这是一种完成您似乎想要做的事情的方法

import re    
def is_abbrev(abbrev, text):
    pattern = ".*".join(abbrev.lower())
    return re.match("^" + pattern, text.lower()) is not None

插入符号确保缩写的第一个字符与单词的第一个字符匹配，对于大多数缩写来说应该是正确的。

编辑：您的新更新稍微改变了规则。通过使用"(|.*\s)"而不是".*"缩写中的字符，仅当它们彼此相邻或下一个字符出现在新单词的开头时才会匹配。

fck这将与正确匹配FC Kopenhavn，但fco不会。但是，匹配不起作用aik，因为这allmanna idrottskluben需要瑞典语的知识，而且不是那么简单。

这是经过少量修改的新代码

import re    
def is_abbrev(abbrev, text):
    pattern = "(|.*\s)".join(abbrev.lower())
    return re.match("^" + pattern, text.lower()) is not None
于 2011-09-07T10:05:03.300 回答
4

@Ocaso Protal在评论中说how should you decide that aik is valid, but aid is not valid?，他是对的。

我想到的算法是使用word threshold（用空格分隔的单词数）。

words = string.strip().split()
if len(words) > 2:
   #take first letter of every word
elif len(words) == 2:
   #take two letters from first word and one letter from other
else:
   #we have single word, take first three letter or as you like

你必须定义你的逻辑，你不能盲目地找到缩写。

于 2011-09-07T10:28:14.623 回答
0

您的算法似乎很简单-缩写是所有大写字母的串联。所以：

upper_case_letters = "QWERTYUIOPASDFGHJKLZXCVBNM"
abbrevation = ""
for letter in word_i_want_to_check:
    if letter in letters:
        abbrevation += letter
for abb in _list_of_abbrevations:
    if abb=abbrevation:
        great_success()
于 2011-09-07T09:28:41.287 回答
0

这可能已经足够好了。

def is_abbrevation(abbrevation, word):
    lowword = word.lower()
    lowabbr = abbrevation.lower()

    for c in lowabbr:
        if c not in lowword:
            return False

    return True

print is_abbrevation('fck', 'FC Kopenhavn')
于 2011-09-07T09:30:00.700 回答