問題タブ [pattern-matching]

私は推論エンジンを開発しています。これは、基本的に、特定の瞬間の世界の表現である特定の数の「事実」を持っていることを意味します。事実 (通常は開始状態と目標状態の 2 つだけです) とともに、多くのルールがあります (特定の問題については文字通り数百になる場合もあります)。推論エンジンの目的は、開始状態と一連のルールを指定して、許容可能な目標状態の 1 つへの最短パスを見つけることです。これは、DFS、BFS、A* などのいくつかのアルゴリズムで実行できます。プログラムの基本構造は次のとおりです。

ルールでは、LHS (> の前の部分)は、「値」に等しいファクト内のすべての属性に一致します。factnameこの場合は 1 つだけですが、複数ある場合もあります。つまり、変数を解決する必要があり (多くの場合、同じ事実に対して複数回)、ルールの LHS には複数の条件が設定されているか、適切な優先度の解析が行われている可能性があります。

問題は、この種の変数を効率的に解決する方法はありますか? 私が今行っていることは、実際のすべての属性を反復処理することであり、基本的に、バランスの取れていない非常に大きな n-ary ツリーを生成しています。これは、特に上記の条件を考えると非常に遅いです。

この種のパターンマッチングの論文へのポインタが欲しい

SQL Server データベースに 2 つのフィールドを持つテーブルがあり、asp.net アプリケーションが '@SearchString' パラメータを使用してストアド プロシージャを呼び出し、ストアド プロシージャは @Searchstring 値が 2 つのフィールドの連結で見つかったすべてのレコードを検索しますテーブル、それらを 'Field1' および 'Field2' と呼びます

したがって、ロジックは次のようになります (実際のクエリを単純化しました)。

このかなり基本的なマッチング アルゴリズムを改善して、一致するレコードがそれほど制限されないようにしたいと考えています。たとえば、ユーザーが「DOG HOUSE」をパラメーターとして入力すると、既存の SP のかなり基本的なロジックによって、正確な文字列が見つかったレコードが返されます。文字列が正確に隣り合っていなくても、「DOG」と「HOUSE」だけのレコードも返すようにしたいと思います。

「最良の一致」に関してレコードをランク​​付けする方法があればさらに良いでしょう。つまり、「DOG HOUSE」が見つかった場合は完全一致であり、「DOG」と「HOUSE」が見つかった場合は 2 番目です。ベスト マッチ、「犬だが「家」または「家」ではなく、「犬」ではない場合」など。

私が望むことの多くを行う一般的なアルゴリズムはありますか?

私はETSを学んでいます。やった：

次に、次のように入力しました。

しかし、取得する代わりに8-私は取得しています：["\b"]出力として！

2つの異なるデータソース間で人の名前を照合するために使用できるツールまたは方法はありますか？

システムには他の共通情報がなく、多くの場合、名前の入力方法が異なります。

完全に一致しない例：

キングジュニア、マーティンルーサー=キング、マーティン（サフィックスを除く）
アービング、ドクターJ. =アービング、J。（プレフィックスを除く）
オバマ、バラクフセイン=オバマ、バラク（ミドルネームを除く）
プフンストゥフ、HR =プフンストゥフ、ハイバネレンメイ（略語に一致）
Tankengine、Thomas = Tankengine、Tom（一般的なニックネームに一致）
Flair、Rick "the Natureboy" = Flair、Natureboy（ニックネームに一致）

文字列があり、その文字列を検証して、'/''\''＆'';'などの特定の文字が含まれていてはならないようにします。など...どうすれば一度にすべてを検証できますか？

私はこれを繰り返し行っていることに気づきます。

そのため、いくつかのボタンにクリックイベントを適用したいので、クリックイベントハンドラーにユーザーIDが必要です。2番目の試合を回避する方法はありますか？

ありがとう。

入力文字列 (URL) を、単純なワイルドカードをサポートする文字列ルールの大規模なセット (1k から 250k の範囲) と照合する必要があります。

ワイルドカード サポートの要件は次のとおりです。

ワイルドカード (*) は、URL の「一部」のみを置き換えることができます。これは、ドメイン、パス、およびパラメーターのフラグメントです。たとえば、「*.part.part/*/part?part=part&part=*」のようになります。この規則の唯一の例外は、「/*」がスラッシュの後の任意のものと一致する必要があるパス領域です。

例:

• *.site.com/* -- sub.site.com/home.html、sub2.site.com/path/home.html と一致する必要があります
• sub.site.*/path/* -- sub.site.com/path/home.html、sub.site.net/path/home.html と一致する必要がありますが、sub.site.com/home.html とは一致しません。

追加要件:

• 高速ルックアップ (「高速」は相対的な用語であることは理解しています。最大 250k のルールを考えると、可能であれば 1.5 秒以内に収まります。 )
• 最新のデスクトップの範囲内で動作します (例: サーバーの実装ではありません)。
• 入力文字列を指定して 0:n の一致を返す機能
• マッチにはルールデータが添付されます

そのようなタスクに最適なシステム/アルゴリズムは何ですか? ルール自体を SQLite データベースに格納して、C++ でソリューションを開発します。

そのため、文字列値 (サードパーティ ツールから入力されたキーワード) を含むテーブルに列があります。私は、おそらく単一の値に正規化できる類似の値のクラスターを識別する自動ツールに取り組んでいます。たとえば、「Firemen」/「Fireman」、「Isotope」/「Asotope」、「Canine」/「Canines」などです。

レーベンシュタイン距離を計算するアプローチは、文字列の操作/比較が多すぎて、SQL インデックスを十分に活用できない可能性があるという事実を除けば、理想的です。

列の Left(X) 文字でインクリメンタルにグループ化することを検討しました。これは、インデックスの使用を最大化するためのそれほど悪くない方法ですが、このアプローチは、単語の最後に違いがある単語を見つける場合にのみ効果的です。 .

SQL でこの問題を効率的に解決するための良いアイデアはありますか?

注: この質問は ( Finding how similar two strings are ) と非常によく似ていますが、ここでの違いは、SQL でこれを効率的に行う必要があることです。

Base64 文字でいっぱいのさまざまな長さの文字列があります。実は音声認識データで、曲ごとに異なります。

これらの文字列の一部を簡単に比較するために、それらを 16 文字の部分文字列に分割します。（これは曲の約 1 秒です）しかし、場合によっては、これらを直接比較することはできません..私はそれらを測定する必要があります.

たとえば、' ' と ' ' との比較は、' hellohellohelloo'と ' ' の比較hallohellohellooよりも近い値を取得する必要があります。hellohellohellooherehellohelloo

アルゴリズムや理論はありますか

編集：申し訳ありませんが、私はここにいるのは初めてです:)そして、私は自分自身を明確にすることができませんでした。ここに私を明確にし、アイデアを提案するいくつかのコメントがあります。

コメント 1:

実際、私はレーベンシュタイン距離について知っていますが、問題は、2 つの文字列を比較するたびに比較行列を作成する必要があり、検索プロセスが遅くなることです。たとえば、hello を 4444 に変換し、hallo を 4443 に変換できれば、数値のインデックスを作成するだけで、「hello」のレコードがどれだけ近いかを判断できます。

コメント 2:

たぶん、基本の固定長文字列を決定し、それらからの距離値を文字列のインデックス値として保存する必要があります。それはただのアイデアですか？

関数型プログラミング言語（Haskell / F＃/ Caml）のパターンマッチング機能を使用して、同じ値を複数回照合できるかどうか疑問に思いました。

次の例を考えてみてください。

最初のバリアントは、関数が2つの類似した値（に格納される）で呼び出されたときに呼び出されますa。

より便利なアプリケーションはこれです（ASTを単純化する）。

しかし、Haskellはこれらのコードを拒否し、定義の競合についてa警告します-関数が同じ値を取得したかどうかを確認する代わりに、明示的なcase/if-checksを実行する必要があります。照合したい変数が複数回発生することを示すトリックはありますか？