問題タブ [string-matching]

Javascriptの正規表現match（）の結果の文字列内の（開始）文字位置を取得する方法はありますか？

率直に言って、これは宿題です。そうは言っても、それは非常にオープンエンドであり、この問題（または一般的な並列アルゴリズム）について考え始める方法についてのガイダンスはほとんどありません。完全な解決策ではなく、正しい方向へのポインタが欲しいのですが。役立つかもしれないどんな読書も同様に素晴らしいでしょう。

私は、並列アルゴリズムを使用して、大量のテキストで最初に出現するパターンを一致させる効率的な方法に取り組んでいます。パターンは単純な文字マッチングであり、正規表現は含まれていません。私はなんとかすべての一致を見つけるための可能な方法を思いついたが、それは私がすべての一致を調べて最初のものを見つけることを必要とする。

だから問題は、プロセス間でテキストを分割し、そのようにスキャンすることにもっと成功するでしょうか？または、j番目のプロセスがパターンのj番目の文字を検索する、ある種のプロセス同期検索を行うのが最善でしょうか？その後、すべてのプロセスが一致に対してtrueを返す場合、プロセスは上記のパターンに一致する位置を変更して再び上に移動し、すべての文字が一致するまで続行してから、最初の一致のインデックスを返します。

私がこれまでに持っているものは非常に基本的なものであり、おそらく機能しません。私はこれを実装しませんが、どんなポインタでもいただければ幸いです。

pプロセッサ、長さtのテキスト、長さLのパターン、および使用されるLプロセッサの上限の場合：

私は、UTF-8 でエンコードされた 2 つのドキュメントの類似性について最終的な判断を下さなければならない Java ソフトウェアを作成しています。

2 つのドキュメントは、日付、場所、作成者などの多くの共通点があるため、同じか、互いにわずかに異なる可能性が非常に高くなりますが、それらのテキストが本当にそうであるかどうかを決定します。

2 つのドキュメントのテキストは非常に似ているか、まったく似ていないことが予想されるため、類似性のしきい値をかなり厳密に設定できます。たとえば、2 つのドキュメントは、90% の単語が共通している場合にのみ類似していると言えますが、短いテキストでも長いテキストでも同じように機能する、より堅牢なものが必要です。

要約すると、私は持っています：

• 非常に似ているか、まったく似ていない 2 つのドキュメント。
• 2 つのドキュメントが類似している可能性が高い
• ドキュメントは長いもの (いくつかの段落) と短いもの (数文) の両方があります。

文字列マッチング関数の大きな配列を持つsimmetricsを試しましたが、使用可能なアルゴリズムについての提案に最も興味があります。

私が持っている可能性のある候補は次のとおりです。

• レーベンシュタイン: その出力は短いテキストの場合により重要です
• 重複する係数: たぶん、しかし、異なる長さのドキュメントをうまく区別できますか?

また、2 つのテキストがまったく同じである場合にのみ類似していると見なすのはうまくいきません。なぜなら、いくつかの単語だけが異なる文書が類似性テストに合格することを望んでいるためです。

Pythonでこれを行う最短の方法は何ですか？

インデックス=3を返す必要があります

私は長さ25のDNA配列を扱っています（以下の例を参照）。私は230,000のリストを持っており、ゲノム全体（toxoplasma gondii寄生虫）の各配列を探す必要があります。ゲノムの大きさはわかりませんが、23万配列よりはるかに長いです。

たとえば、（AGCCTCCCATGATTGAACAGATCAT）のように、25文字のシーケンスをそれぞれ探す必要があります。

ゲノムは連続した文字列としてフォーマットされます。つまり、（CATGGGAGGCTTGCGGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTTGCGGAGTGCGGAGCCTGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTT....）

どこに何回あるかは気にせず、見つけられるかどうかだけです。
これは簡単だと思います-

しかし、私はまた、任意の場所で間違っている（不一致）と定義されている厳密な一致を見つけて、その場所を1つの場所だけに記録し、その場所を順番に記録します。これをどのように行うのかわかりません。私が考えることができる唯一のことは、ワイルドカードを使用し、各位置でワイルドカードを使用して検索を実行することです。つまり、25回検索します。

例えば、

位置13での不一致との密接な一致。

スピードは3回しかないので大した問題ではありませんが、速ければいいのですが。

これを行うプログラムがあります-一致と部分一致を検索します-しかし、私はこれらのアプリケーションでは検出できないタイプの部分一致を探しています。

これはperlの同様の投稿ですが、シーケンスを比較しているだけで、連続した文字列を検索していません。

関連記事

SSH デバッグ情報を他の入力とは分けて (ログに記録して) 保持したい。ただし、単純に stderr をログ ファイルにリダイレクトすると、SSH からの出力とホスト マシン上のリモート プロセスからの出力を組み合わせる危険があります ( stderr に何かが送信される可能性があります)。

したがって、「debug1」に一致する行のみを除外したいと思います。

ここまでは問題ありませんが、ssh のデバッグ出力は stderr に出力されます。そう...

また失敗！stdout と stderr を混在させたくありません。悪い！

私のような子供は何をしますか？私は名前付きパイプまたはそのような野生のルートに行こうとしていましたが、実際に知る必要があるのは、awk を stderr のみからのパターンに一致させる方法だけです。

2本の弦があります。

String str1="Order Number Order Time Trade Number";

String str2="Order Tm";次に、 str2が str1 のどの部分文字列と一致するかを知りたいです。

「Order Tm」は「Order Time」にも一致するため、正規表現を使用しています。一致が発生したかどうかをブール値で示します。

その後、str1 のようstr2="Order Tm"に返される必要があります。Order Timeは、一致が発生した部分文字列です。

ハッシュマップがあるとしましょう。

オートコンプリート機能を実行しようとしています。ユーザーが「fo」と入力すると、ajaxを介して$hashから3つのキーを取得したいと思います。ユーザーが「for」と入力した場合、キーfortとforkのみを取得したいと思います。これは可能ですか？

私が考えていたのは、ブルートフォース検索の代わりに、バイナリ検索を使用してキーを「f」で分離することでした。次に、ユーザーがクエリを入力するときにインデックスを削除し続けます。これに対するより効率的な解決策はありますか？

編集：ワイルドカードに関して、私が疑問に思っていたのは、$ hash ["f *"]を実行する方法がある場合、「f」で始まるすべてのインデックスを返すことです。

現在、入力を正規表現に一致させる JavaScript でアプリケーションを作成していますが、文字列を正規表現の一部に一致させる方法も見つける必要があります。

例えば：

potentiallyここで、変数の値が式と正確に一致しないことをどうにかして判断する方法を見つける必要がありますが、/^ggg$/より多くの入力があれば、可能性があります!

したがって、たとえばこの場合、potentially変数は ですがg、さらに 2 つg追加すると、正規表現に一致します。/^ggg$/

しかし、 の場合、何文字追加しても式とinvalid一致することはありません。/^ggg$/

では、文字列が特定の正規表現に一致する可能性があるかどうかを判断するにはどうすればよいでしょうか?

各単語間にギャップがない長い一連の音から単語のインスタンス (音の文字列) を分離する必要がある音声認識エンジンをモデル化しようとしています。電話のストリームは、文字の置換/挿入/削除により認識が不十分な可能性があるため、おおよその文字列の一致を行う必要があります。

ただし、マッチングを音声学的に動機づけたい。たとえば、"m" と "n" は音声学的に類似しているため、"m" と "k" に比べて "m" の "n" への置換コストは小さくする必要があります。 "。したがって、[mein] "main" を検索している場合、文字列 [meim] "maim" はコスト 0.1 と一致し、文字列 [meik] "make" と一致します。 、コスト 0.7。同様に、各文字を挿入または削除するためのコストも異なります。文字のペア (x,y) ごとに、x を y に置き換えるコストを与える混同行列を提供できます。ここで、x と y は任意の文字または空の文字列です。

などの近似マッチングを行うツールがあることは知っていますが、agrep私が知る限り、それらは混同行列を入力として取りません。つまり、挿入/置換/削除のコスト= 1 です。私の質問は、混同行列との近似マッチングを行うことができるオープンソース ツールが既に利用可能であるかどうかです。そうでない場合、実装できる優れたアルゴリズムは何ですか?これを達成するには？

編集: 明確にするために、[mein] などの単語のおおよそのインスタンスを [aiammeinlimeiking...] などの長い文字列から分離しようとしています。理想的には、アルゴリズム/ツールは、コスト 0.0 (完全一致) の [mein]、コスト 0.7 (ほぼ一致) の [meik] などのインスタンスを、コストが特定のしきい値を下回るすべての近似文字列一致について報告する必要があります。