問題タブ [pattern-matching]

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

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

そのため、いくつかのボタンにクリックイベントを適用したいので、クリックイベントハンドラーにユーザー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を実行する必要があります。照合したい変数が複数回発生することを示すトリックはありますか？

Composed Regular Expressionsに関して Martin Fowler がまとめた記事を読んでいました。これは、次のようなコードを使用できる場所です。

そして、それを次のようなものに分割します。

またはこれ：

またはこれでも：

これは簡単に実行できるように思えますが、いくつかの利点があるかもしれません。私は決して「正規表現の男」ではなく、自分で作成するのに時間をかけるのではなく、必要な正規表現を見つけるためにネットを検索することがよくあります。特定の問題にぴったりの正規表現を見つけたので、それをコピーして貼り付け、テストして、宣伝どおりに機能することを確認します。次に、それが何をするかを説明するコメントをドロップするかもしれません。しかし、その後、私は人生でより大きく、より良いものに向かいます.

マーティン・ファウラーの議論で説明されている方法で正規表現パターンを分割すると、実際にコメントよりも理解しやすくなるかどうか疑問に思っていますか? 結局のところ、コードにはいまだ醜い正規表現が残っていますが、それは多くの部分に分かれています。その式を拡張する必要がある場合...これは、正規表現が何をしているのかを本当に理解するのにどのように役立ちますか?

根っからの perl 連中が正規表現パターンを愛していることは知っています。しかし、他のすべてのプロジェクトで 1 回以上正規表現を扱わない人 (質問) にとって、正規表現パターンをより小さなビットに分割することは、多かれ少なかれ読みやすいと思いますか? プロジェクトでこの概念を採用し、有用だと感じた人はいますか? ...役に立たない？

ゼロと1の線形リストがあり、複数の単純なパターンを照合して最初の出現を見つける必要があります。たとえば、長さ800万のリスト内0001101101で01010100100、、、またはを検索する必要がある場合があります。10100100010どちらかが最初に出現したものを見つけて、それが発生したインデックスを返すだけです。ただし、大きなリストに対してループとアクセスを実行するとコストがかかる可能性があるため、何度も実行したくありません。

行うよりも速い方法はありますか

編集：ところで、私は上記の擬似コードに従ってこのプログラムを実装しました、そしてパフォーマンスはOKですが、素晴らしいものは何もありません。プロセッサのシングルコアで1秒間に約600万ビットを処理すると推定しています。私はこれを画像処理に使用していますが、数千の8メガピクセルの画像を処理する必要があるため、少しでも役立ちます。

編集：明確でない場合は、ビット配列を使用しているため、1と0の2つの可能性しかありません。そしてそれはC++です。

編集： BMおよびKMPアルゴリズムへのポインターをありがとう。BMのウィキペディアのページに、

アルゴリズムは、検索対象の文字列（キー）を前処理しますが、検索対象の文字列は前処理しません（検索対象の文字列を前処理し、繰り返し検索することで前処理の費用を償却できる一部のアルゴリズムとは異なります）。

それは面白そうに見えますが、そのようなアルゴリズムの例は示されていません。そのようなものも役立ちますか？