問題タブ [string-matching]

次のデータ要素を持つ人々でいっぱいのデータベースがあるとしましょう。

• PersonID（意味のない代理自動番号）
• ファーストネーム
• ミドルネームのイニシャル
• 苗字
• NameSuffix
• 生年月日
• AlternativeID（SSN、Militarty IDなど）

私はあなたが考えることができるこれらの情報のあらゆる合理的なバリエーションであらゆる種類のフォーマットからたくさんのデータフィードを受け取ります。いくつかの例は次のとおりです。

• フルネーム、DOB
• フルネーム、最後の4つのSSN
• 最初、最後、DOB

このデータが入ってくると、それに合わせて何かを書く必要があります。80％を超える一致率を取得する必要はありません。自動一致の後、誰かが手動で一致させるために、不確実な一致をWebページに表示します。

複雑さのいくつかは次のとおりです。

1. 一部のデータ一致は他のデータよりも優れているので、それらに重みを付けたいと思います。たとえば、SSNが完全に一致しているが、誰かがミドルネームを使用しているために名前がオフになっている場合、名前が完全に一致しているがSSNがオフになっている場合よりも、その一致にはるかに高い信頼値を割り当てたいと思います。
2. 名前の照合にはいくつかの問題があります。JohnDoeJrはJohnDoeIIと同じですが、John Doe Sr.とは異なります。JohnDoeと他の情報がない場合は、判断する方法がないため、システムが1つを選択しないようにする必要があります。誰を選ぶか。
3. 名のマッチングは本当に難しいです。ボブ/ロバート、ジョン/ジョン/ジョナトン、トム/トーマスなどがいます。
4. FullName + DOBのフィードがあるからといって、すべてのレコードのDOBフィールドが入力されているわけではありません。比類のないDOBが一致するスコアを殺すという理由だけでリンケージを見逃したくありません。フィールドが欠落している場合、マッチングに使用できる要素からそのフィールドを除外したいと思います。
5. 誰かが手動で一致する場合、私は彼らの一致が将来のすべての一致に影響を与えることを望みます。したがって、同じ正確なデータを再度取得した場合、次回は自動的に一致させない理由はありません。

SSISにはあいまい一致があることを確認しましたが、現在SSISを使用していません。また、バージョン管理がかなり厄介でほぼ不可能であるため、ツールの最初の選択肢ではありません。しかし、それが最高の場合は、教えてください。それ以外の場合、このタイプの問題に使用した（できれば無料、できれば.NETまたはT-SQLベースの）ツール/ライブラリ/ユーティリティ/テクニックはありますか？

大量のデータで文字列照合を行っています。

編集：私はいくつかのオントロジーテキストファイルと大きなリストに含まれている単語を一致させています。オントロジーから各ファイルを取得し、各ファイル行の3番目の文字列とリストの任意の単語との一致を検索します。

私がしなければならないのは純粋なマッチングではない（結果が悪い）という事実を監視するのを間違えましたが、文字列が別の文字列内に含まれている場合にも結果を返す、より緩いマッチング関数が必要です。

私はこれをRadixTrieで行いました。非常に高速でうまく機能しましたが、トライは完全一致のみを返すため、今では私の作業は役に立たないと思います。：/

• これを行うアルゴリズムのタイプは文字列検索アルゴリズムですか？
• 誰かが彼が経験したいくつかのJava実装を提案できますか？

アルゴリズムは高速である必要がありますが、最優先事項ではなく、速度と複雑さで妥協します。

すべてのアドバイス/例/説明/リンクにとても感謝しています！

ありがとうございました！

テーブルにテキスト データ型のフィールドがあります。

次の 2 つの SQL クエリのパフォーマンスに違いはありますか。

これらのクエリの実行を実装する場合、これが必要になると思います。

2 つの正規表現 (xyz* と *zyx) を一致させる必要があります。

文字列 chars を最初から 1 つずつチェックする必要があります。

最初のクエリでは、一致するかどうかを確認するために最初の 3 文字を読み取る必要がありますが、2 番目のクエリでは、一致が発生したかどうかを判断するために、文字列の末尾を取得するまで読み取る必要があります。しかし、文字列の長さがどこかに格納されている場合、最後の 3 文字を直接読み取ることができ、最初のケースと同様のパフォーマンスが得られます。

私の質問は、mysql や oracle などの商用データベースで、クエリの実行のパフォーマンスに違いがあるかどうかです。

受信したそれほど長くないテキストを検索して、特定の文字列が出現するかどうかを調べる必要があります。文字列はセッション全体で一定であり、多くはありません (~10)。さらに単純化すると、どの文字列も他の文字列には含まれません。

現在、とのブースト正規表現マッチングを使用していstr1 | str2 | ...ます。このタスクのパフォーマンスは重要なので、改善できないかと考えています。ブースト担当者よりも優れたプログラミングができるわけではありませんが、専用の実装は一般的な実装よりも効率的です。

文字列は長期間にわたって一定のままであるため、状態遷移表のようなデータ構造を事前に構築する余裕があります。

たとえば、文字列がabcx、 、bcyおよびczであり、これまで読んだabcことがある場合、 を意味する結合状態にあるはずyou're either 3 chars into string 1, 2 chars into string 2 or 1 char into string 1です。x次に、次を読み取るとstring 1 matched状態などに移動し、以外の文字xyzは初期状態に移動し、に戻る必要はありませんb。

どんなアイデアや参考文献も大歓迎です。

なんらかの理由で、プログラムが57802レコードのファイルの反復処理を停止するという問題が発生しました。ハートビートセクションを挿入して、それがどの行にあるかを確認できるようにしましたが、それが役に立ったのですが、なぜここで停止するのかがわかりません。メモリの問題だと思いましたが、6GBのメモリコンピュータで実行しただけで停止しました。

私が下でやっていることをするためのより良い方法はありますか？私の目標は、ファイルを読み取ることです（ファイルを送信する必要がある場合は、15 MBのテキストログを使用できます）。正規表現に基づいて一致するものを見つけ、一致する行を印刷します。もっと来ますが、それは私が得た限りです。私はPython2.6を使用しています

どんなアイデアでも助けになり、コメントもコーディングできます！私はPythonの初心者で、まだ学習中です。

これは、失敗する行57802です。

これは一致する行です：

最初の5行だけのサンプルデータ：

先週、インターンシップの面接を受け、大規模なデータベースで特定の文字列を検索することについて質問されました。インタビュー中、私はそれについてまったく無知でしたが、「マルチレベルハッシュ」と答えただけで、それが私が知っている唯一のヒントであり、最高の時間効率を持っていました。少しグーグルした後、彼が期待した答えはそれだったと思いますサフィックスツリー。検索中にサフィックスツリーを構築するためのアルゴリズムを見つけ、サフィックスツリーの構築方法に関する研究論文さえありました!! では、特にインタビュー時に、文字列マッチング アルゴリズムのサフィックス ツリーを実装することは本当に可能でしょうか?

誰かがそれに光を当てることができれば素晴らしいでしょう。

前もって感謝します

私はショッピング比較サイトを開発していますが、プロジェクトは非常に進んだ段階にあります。さまざまなアフィリエイトネットワークからのマーチャントフィードを使用して、毎日5,000万の製品にインデックスを付けています。パフォーマンスのボトルネックの大部分を含め、私が抱えていた問題のほとんどはすでに解決されています。

私の問題は何ですか：まず、drupalでapache solrを使用していますが、この問題はdrupalまたはsolrに固有のものではありません。知識がなくても、問題ありません。

私たちは2000以上の異なる商人から製品フィードを受け取ります、そしてそれらのフィードは混乱しています。それらには特定のパターンはなく、各マーチャントは希望する方法でフィードを送信します。これに関してはすでに多くの問題を解決しましたが、1つ残っています。ファセットブラウジング機能の分類用語を正規化します。

Webサイトに「NarrowbyBrands」ブラウジングファセットがあるとします。ここで、100のマーチャントがMicrosoftの製品を提供するとします。ここで問題が発生します。データフィード「Microsoft」の「ブランド」列に入力するマーチャント、「Microsoft、Inc。」、「Microsoft Corporation」、「Products from Microsoft」など、マーチャントと最悪の間に特定のパターンはありません。 、一部の個々の商人は非常にずさんなので、同じデータフィードで同じブランドに対して異なる文字列を持っています。

これらの異なるブランドすべてがナビゲーションに表示されることは望ましくありません。インポートしたブランドを「good」ブランドテーブル（「MicrosoftCorporation」->「Microsoft」、「Products fromMicrosoft」->「Microsoft」など）に手動でマッピングするという問題に対する手動の解決策があります。データベースには10,000のブランドのようなものがあり、これは実行可能です。問題は、「作者」のような大きなものが付属している場合です。書籍をシステムにインポートすると、80万人を超える著者がいて、同じ問題が発生します。これは、手動マッピングでは実行できません。問題は同じです：「トム・マイク・アポストル」、「トム・M・アポストル」、「アポストル、トム・M」など。

許容できる精度（85％-95％の精度）でこの問題を自動的に解決する良い方法を知っている人はいますか？

助けてくれてありがとう！

これまでの完全なコードは次のとおりです。

ローミング オブジェクトとローカル オブジェクトを設定するセクションでは、「game1」以外のものとは決して一致しないと言っています。

「printf」を実行して、ローカルおよびローミング オブジェクトとのマッチングの前後を確認しました...両方の printf コマンドでゲームプリントが正しく表示されますが、game1 以外のものとは一致しません...よくわかりません間違えたところ。

Pythonを使用してEMPが辞書に存在するかどうかを確認する方法

この目的のために組み込みのタグがあります。

ユーザーがテキストボックスに文字を入力すると、入力した文字で始まる文字列がリスト形式で表示されます。リストから選択されたアイテムは、テキストボックスに取り込まれます。

PS: 使用可能な例とデモでは、入力された文字を含む文字列が表示されます。しかし、入力した文字で始まる文字列のみを表示したいのです。