6

アプリのある時点で、いくつかの文字列をパターンと照合する必要があります。サンプル文字列の一部が次のようになっているとします。

  1. こんにちは、ジョン。
  2. 今日はなんて素敵な日でしょう！
  3. ジョン、今日の夕日は素敵ですね。
  4. ジョン、今日リンダに会える？

これらの文字列のほとんど (すべてではない) は、次のように事前定義されたパターンからのものです。

  1. 「やあ、%s。」
  2. 「今日はなんて素敵な日でしょう！」
  3. 「今日の夕日、%s ですね。」
  4. 「今日 %s に会いませんか、%s?」

このパターンのライブラリは拡大し続けています (現在約 1,500) が、手動で維持されています。ただし、入力文字列 (最初のグループ) はほとんど予測できません。それらのほとんどはいずれかのパターンに一致しますが、一致しないものもあります。

そこで、私の質問は次のとおりです。(最初のグループの) 文字列が入力として与えられた場合、それがどのパターン (既知の 2 番目のグループ) に一致したかを知る必要があります。何も一致しない場合は、それを教えてくれる必要があります。

解決策には、パターンから正規表現を構築し、どれが一致したかを繰り返し確認することが含まれると思います。ただし、これらの正規表現を構築するコードがどのように見えるかはわかりません。

注: ここで指定した文字列は、説明のためのものです。実際には、文字列は人間が生成したものではありませんが、私が制御していないシステムから上に示したように、コンピューターが生成した人間に優しい文字列です。手動で入力しないため、タイプミスやその他の人的ミスなどを心配する必要はありません。一致するパターンを見つけるだけです。

注 2: 正規表現の作成が容易になる場合は、パターン ライブラリを他の形式に変更できます。printf スタイル %s を使用した現在の構造は、確定していません。

4

6 に答える 6

3

私はこれを解析の問題として見ています。パーサー関数は文字列を受け取り、それが有効かどうかを判断するという考え方です。

find指定されたパターンの中で文字列が有効であれば、文字列は有効です。つまり、すべてのパターンのインデックスが必要です。インデックスは全文インデックスである必要があります。また、単語の位置に応じて一致する必要があります。例えば。入力の最初の単語がパターンの最初の単語の中に見つからない場合は、短絡する必要があります。any一致、つまり%sパターンを処理する必要があります。

解決策の 1 つは、パターンをメモリ内データベース (redis など) に配置し、全文インデックスを作成することです。（これは単語の位置によっては一致しません）が、入力を単語に分割して検索することで、正しいパターンに絞り込むことができるはずです。メモリ内のデータベースが小さいため、検索は非常に高速になります。また、最も近い一致を探していることに注意してください。1 つまたは複数の単語が一致しません。一致の最大数は、必要なパターンです。

さらに良い解決策は、独自のインデックスを辞書形式で生成することです。JavaScript オブジェクトとして指定した 4 つのパターンのインデックスの例を次に示します。

{
    "Hi": { "there": {"%s": null}},
    "What: {"a": {"lovely": {"day": {"today": null}}}},
    "Lovely": {"sunset": {"today": {"%s": {"isnt": {"it": null}}}}},
    "Will": {"you": {"be": {"meeting": {"%s": {"today": {"%s": null}}}}}}
}

このインデックスは、単語の位置に従って再帰的に降順です。したがって、最初の単語を検索し、見つかった場合は、最初の単語によって返されたオブジェクト内で次の単語を検索します。特定のレベルの同じ単語には、1 つのキーしかありません。大文字と小文字も一致させる必要がありanyます。これは、メモリ内で目がくらむほど速くなるはずです。

于 2013-05-07T11:56:36.063 に答える
1

Noufal のソリューションに似ていますが、一致したパターンまたは None を返します。

import re

patterns = [
    "Hi there, %s.",
    "What a lovely day today!",
    "Lovely sunset today, %s, isn't it",
    "Will you be meeting %s today, %s?"
]

def make_re_pattern(pattern):
    # characters like . ? etc. have special meaning in regular expressions.
    # Escape the string to avoid interpretting them as differently.
    # The re.escape function escapes even %, so replacing that with XXX to avoid that. 
    p = re.escape(pattern.replace("%s", "XXX"))
    return p.replace("XXX", "\w+")

# Join all the pattens into a single regular expression.
# Each pattern is enclosed in () to remember the match. 
# This will help us to find the matched pattern.
rx = re.compile("|".join("(" + make_re_pattern(p) + ")" for p in patterns))

def match(s):
    """Given an input strings, returns the matched pattern or None."""
    m = rx.match(s)
    if m:
        # Find the index of the matching group. 
        index = (i for i, group in enumerate(m.groups()) if group is not None).next()
        return patterns[index]

# Testing with couple of patterns
print match("Hi there, John.")
print match("Will you be meeting Linda today, John?")
于 2013-05-07T07:40:46.413 に答える
0

これは sscanf の仕事かもしれません。js での実装があります: http://phpjs.org/functions/sscanf/ ; コピーされる関数は次のとおりです: http://php.net/manual/en/function.sscanf.php。

用意されている弦をあまり変えずに使えるはずですが、性能に疑問があります。

于 2013-05-07T07:24:54.840 に答える