3

私は、Python で順次パターン マッチングのアルゴリズムを実装する必要があるという状況に陥っています。何時間も検索しても、インターネット上で機能するライブラリ/スニペットが見つかりません。

問題定義:

関数 sequential_pattern_match を実装します

入力: トークン (順序付けられた文字列のコレクション)

出力: タプルのリスト、各タプル = (トークンの任意のサブコレクション、タグ)

ドメインの専門家が、通常は正規表現を使用して一致ルールを定義します

テスト (トークン) -> タグまたはなし

例：

入力: [「シンガポール」、「Python」、「ユーザー」、「グループ」、「は」、「ここ」]

出力: [(["シンガポール", "Python", "ユーザー", "グループ"], "組織"), ("ある", 'O'), ("ここ", 'O')]

「O」は一致しないことを意味します。

競合解決規則:

  1. 最初に表示される一致が優先されます。たとえば、「シンガポールの不動産販売」の場合、資産として「シンガポールの不動産」、イベントとして「不動産の販売」という 2 つの競合する一致が可能である場合、最初のものが使用されます。
  2. 長い一致は、短い一致よりも優先されます。たとえば、組織としての「Singapore Python User Group」は、場所としての「Singapore」+言語としての「Python」の個々の一致よりも優先されます。

アルゴリズムとデータ構造に関する私の専門知識により、これが私の実装です。

from itertools import ifilter, imap


MAX_PATTERN_LENGTH = 3

def test(tokens):
    length = len(tokens)
    if (length == 1):
        if tokens[0] == "Nexium":
            return "MEDICINE"
        elif tokens[0] == "pain":
            return "SYMPTOM"
    elif (length == 2):
        string = ' '.join(tokens)
        if string == "Barium Swallow":
            return "INTERVENTION"
        elif string == "Swallow Test":
            return "INTERVENTION"
    else:
        if ' '.join(tokens) == "pain in stomach":
            return "SYMPTOM"

def _evaluate(tokens):
    tag = test(tokens)
    if tag:
        return (tokens, tag)
    elif len(tokens) == 1:
        return (tokens, 'O')

def _splits(tokens):
    return ((tokens[:i], tokens[i:]) for i in xrange(min(len(tokens), MAX_PATTERN_LENGTH), 0, -1))

def sequential_pattern_match(tokens):
    return ifilter(bool, imap(_halves_match, _splits(tokens))).next()

def _halves_match(halves):
    result = _evaluate(halves[0])
    if result:
        return [result] + (halves[1] and sequential_pattern_match(halves[1]))

if __name__ == "__main__":
    tokens = "I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium".split()
    output = sequential_pattern_match(tokens)
    slashTags = ' '.join(t + '/' + tag for tokens, tag in output for t in tokens)
    print(slashTags)
    assert slashTags == "I/O went/O to/O a/O clinic/O to/O do/O a/O Barium/INTERVENTION Swallow/INTERVENTION Test/O because/O I/O had/O pain/SYMPTOM in/SYMPTOM stomach/SYMPTOM after/O taking/O Nexium/MEDICINE"

    import timeit
    t = timeit.Timer(
        'sequential_pattern_match("I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium".split())',
        'from __main__ import sequential_pattern_match'
    )
    print(t.repeat(3, 10000))

もっと速くできないと思います。残念ながら、関数型で書かれており、Python には適していない可能性があります。オブジェクト指向または命令型スタイルでより高速な実装を実現できますか?

(注: C で実装した方が高速になると確信していますが、現時点では Python 以外の言語を使用する予定はありません)

4

2 に答える 2

1 
def sequential_pattern_match(tokens):
    for first, rest in _splits(tokens):
        x = _halves_match(first, rest)
        if x:
            return x

def _splits(tokens):
    for i in xrange(min(len(tokens), MAX_PATTERN_LENGTH), 0, -1):
        yield tokens[:i], tokens[i:]

def _halves_match(first, rest):
    tag = test(first)
    if tag:
        return [(first, tag)] + (rest and sequential_pattern_match(rest))

def test(tokens):
    length = len(tokens)
    if length == 1:
        if tokens[0] == "Nexium":
            return "MEDICINE"
        elif tokens[0] == "pain":
            return "SYMPTOM"
        else:
            return "O"
    elif length == 2:
        if tokens == ["Barium", "Swallow"]:
            return "INTERVENTION"
        elif tokens == ["Swallow", "Test"]:
            return "INTERVENTION"
    elif tokens == ["pain", "in", "stomach"]:
        return "SYMPTOM"

を単純なループifilterに置き換えました。ループ付きのジェネレーター式。imapforforyield

私のマシンで短縮された時間:

  • 1.02694065435 -> 0.708227394544 (Python 2.7.5)
  • 1.1575780184 -> 0.425939527209 (PyPy 2.1)
于 2013-10-13T08:19:49.557 に答える
0

あなたのソリューションはエレガントではありません。htql.net の htql.RegEx の使用を検討してください。問題の部分的な解決策は次のとおりです。

tokens = "I went to a clinic to do a Barium Swallow Test because I had pain in stomach after taking Nexium".split()
symptoms = ['Nexium', 'pain', 'Barium Swallow', 'Swallow Test', 'pain in stomach']

import htql
a=htql.RegEx()
a.setNameSet('symptoms', symptoms)

a.reSearchList(tokens, '&[ws:symptoms]')
# [['Barium', 'Swallow'], ['pain', 'in', 'stomach'], ['Nexium']]

a.reSearchList(tokens, '&[ws:symptoms]', useindex=True)
# [(8L, 2L), (14L, 3L), (19L, 1L)]

これをより複雑なシナリオに簡単に拡張できます。

于 2013-10-15T14:08:30.873 に答える