4

str1 が str2 のプレフィックスかどうかを判断する簡単な関数を書き留めました。これは非常に単純な関数で、(JS では) 次のようになります。

function isPrefix(str1, str2) // determine if str1 is a prefix of a candidate string
{
    if(str2.length < str1.length) // candidate string can't be smaller than prefix string 
        return false;

    var i = 0;
    while(str1.charAt(i) == str2.charAt(i) && i <= str1.length)
        i++;
   if(i < str1.length) // i terminated => str 1 is smaller than str 2
        return false;
    return true;
}

ご覧のとおり、プレフィックス文字列の全長をループして、候補文字列のプレフィックスであるかどうかを判断します。これは、複雑さが O(N) であることを意味します。これは悪くありませんが、プレフィックス文字列がプレフィックスの一部として含まれる文字列を決定するためにループを検討する巨大なデータ セットがある場合、これは問題になります。これにより、複雑さが O(M*N) のように倍増します。ここで、M は特定のデータ セット内の文字列の総数です。良くない。

私はインターネットを少し調べて、最良の答えはパトリシア/基数のトライであると判断しました。文字列がプレフィックスとして格納される場所。それでも、文字列を挿入/検索しようとすると、前述のプレフィックスゲージ機能を使用すると、文字列の照合にかなりのオーバーヘッドが発生します。

プレフィックス文字列「rom」と候補単語のセットがあるとします

var dataset =["random","rapid","romance","romania","rome","rose"];

基数トライでこれが欲しい：

         r
       /    \
     a       o
    / \     / \
ndom pid  se  m
             / \
           an   e
          /  \
        ia   ce

これは、すべてのノードに対して、プレフィックス一致関数を使用して、インデックスのプレフィックス文字列に一致する値を持つノードを特定することを意味します。どういうわけか、この解決策はまだ難しいようで、私にはあまりうまくいきません。もっと良いものはありますか、とにかくコアプレフィックスマッチング機能を改善できますか?

4

2 に答える 2

10

2 つの異なる問題があるようです。

1 つは、文字列が別の文字列のプレフィックスとして含まれているかどうかを判断することです。これには、言語の文字列ライブラリに既に実装されている関数を使用することをお勧めします。JavaScriptでは、これを行うことができます

if (str2.indexOf(str1) === 0) {
    // string str1 is a prefix of str2
}

こちらの String.indexOf のドキュメントを参照してください: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/indexOf

もう1つの問題については、一連の文字列の中で、指定された文字列をプレフィックスとして持つものを見つけて、Trieのようなデータ構造を構築するか、高速なルックアップが必要な場合は、あなたが言及したものを使用する方法のようです。

于 2013-09-04T03:45:49.837 に答える
1

stackoverflow のこのスレッドをチェックしてください -文字列 "StartsWith" 別の文字列をチェックする方法は? . Mark Byers のソリューションは非常に効率的です。また、Javaの場合、組み込みの文字列関数「endsWith」および「startsWith」があります - http://docs.oracle.com/javase/tutorial/java/data/comparestrings.html

于 2013-09-04T05:45:35.697 に答える