1

次のような文字列が与えられた場合:

 var str = "thisisinsane";

次のような辞書からの単語のリストによって支援されます。

 var dic = [ "insane", "i", "is", "sin", "in", "this", "totally" ];

str単語に分割するには？

この文字列には、識別する単語が 3 つあります。しかし、落とし穴を避ける必要があります。ほとんどの場合、それらを避けるために、文の左側を攻撃して、可能な限り長い単語を見つけようとすることができることを私は知っています. 見つかったら、残りの文字列などを攻撃できます。

下 : 入力、考えられる落とし穴、および必要な出力 (右下)。

                      thisisinsane
                          |
                          |
                     (this)isinsane
                     /            \
                    /              \
          (this,i)sinsane         (this,is)insane
              /                     /           \
             /                     /             \
  (this,i,sin)ane          (this,is,in)sane    (this,is,insane)
                                /                   <BEST IS>
                               /                    <THIS ONE>
                       (this,is,in,sane)

最後に、取得したいのは次のとおりです。

 var splited = ["this", "is", "insane"];
4

1 に答える 1

1

これは、左から右に検索を行い、最初に辞書内の最も長い単語に一致する簡単な実装です ( jsfiddle )。ただし、複雑な分野のように聞こえるため、これを独自に実装するのが非常に賢明であるかどうかはわかりません。この主題に関する知識がなくても、このアルゴリズムにはそもそも欠陥があると言えます。既存のライブラリがある場合は、それを探したほうがよいかもしれません。

言うまでもなく、これはすぐにまとめて入力しただけです。パフォーマンスが最適化されておらず (再帰を使用していますが、これは実際にはまったく必要ありません)、広範囲にテストされていません。ただし、サンプルデータと、私がテストしたいくつかのバリエーションでは機能します。完全なコード例を示す場合に備えて、作業の一部を OP に任せたいので、使用したい場合は自由に改善してください。

var splitByDictionary = function (input, dictionary) {
    "use strict";

    // make sure we're going to look for longest-possible matches first
    dictionary.sort( function (a, b) {
        return b.length - a.length;
    } );

    var foundWords = [],
        remaining = input;

    var result = (function match () {
        if( remaining.length === 0 ) {
            return true;
        }

        for( var i = 0; i < dictionary.length; i++ ) {
            if( remaining.substr( 0, dictionary[i].length ) === dictionary[i] ) {
                foundWords.push( dictionary[i] );
                remaining = remaining.substr( dictionary[i].length );

                return match();
            }
        }

        return false;
    })();

    return result ? foundWords : null;
};

var splitted = splitByDictionary( "thisisinsane", ["insane", "i", "is", "sin", "in", "this", "totally"] );
console.log( splitted ); // ["this", "is", "insane"]
于 2013-11-23T00:29:09.517 に答える