1

三分探索木を使用してスペルチェッカーコードを作成しました。TSTで次の可能な単語を見つける方法を誰か教えてください. たとえば、スペル チェッカーで「Manly」という単語を検索し、その単語が TST に存在しない場合に検索したい場合、DO YOU MEAN: "Man" "Mango" のような出力が得られます。.言葉の近くで可能なことを意味する

4

2 に答える 2

1

私は独自のスペル チェッカーを実装しましたが、単純な 3 項トライの代わりに、Peter Kankowski がここで提案しているように 3 項ダグを使用しています。いくつかの詳細と私がそれをどのように行ったかについては、私のブログをご覧ください。ギリシャ語ですが、アイデアを得ることができます。

編集：

わかりました、あなたは正しいです。基本的な考え方は、特定の編集距離に対して事前に作成された候補のリストを使用することです (私にとっては 2 の値で問題ありません)。リストのサイズを縮小するには、ワイルドカード文字を使用できます。もちろん、このようなリストはさまざまな方法で作成できます。私はこのような for/while ループを好みます (たとえば、2 つの置換の候補の場合)。

void Substitute2( vector<wchar_t*>& v, const wstring& w )
{
    size_t len = w.size();
    if ( len < 2 )
        return;
    size_t p1 = 0, p2 = 1;
    while ( p1 < len ) {
        p2 = p1 + 1;
        while ( p2 < len ) {
            wchar_t* chars = new wchar_t[ len + 1 ];
            for ( size_t i = 0; i < len; ++i ) {
                if ( i != p1 && i != p2 ) {
                    chars[ i ] = w[ i ];
                }
            }
            chars[ p1 ] = '?';
            chars[ p2 ] = '?';
            chars[ len ] = '\0';
            v.push_back( chars );
            p2++;
        }
        p1++;
    }
}

候補リストを準備した後、リスト内の各項目を 3 値ダグで簡単に検索すると、スペルミスのある単語の候補が表示されます。

void Search( FileNode* pDict, FileNode* pNode, const wchar_t* Word, wstring Sug, set<wstring>& List )
{
    if ( IsNullLink( pNode, pDict ) )
        return;
    if ( *Word == '?' ) {
        Search( pDict, GetLo( pNode, pDict ), Word, Sug, List );
        Search( pDict, GetEq( pNode, pDict ), Word + 1, Sug + pNode->Char, List );
        Search( pDict, GetHi( pNode, pDict ), Word, Sug, List );
    } else {
        if ( *Word < pNode->Char ) {
            Search( pDict, GetLo( pNode, pDict ), Word, Sug, List );
        } else if ( *Word > pNode->Char ) {
            Search( pDict, GetHi( pNode, pDict ), Word, Sug, List );
        } else {
            if ( pNode->Char == '\0' )
            {
                List.insert( Sug );
            }
            if ( *Word != '\0' ) {
                Search( pDict, GetEq( pNode, pDict ), Word + 1, Sug + pNode->Char, List );
            }
        }
    }
}

注: 辞書は、コンパイルされた (ファイル ベースの) 3 項 DAG です。

于 2015-06-20T12:10:38.180 に答える
0

TST 内の単語の検索は、ツリー内の特定の場所で終了します。この時点から、あなたが生まれた子供以上のものがあるレベルに到達するまで、ツリーのレベルを 1 つ上げることができます。

そのレベルでは、他の可能なパスを選択して、それらの単語を返すことができます。

于 2015-03-19T13:07:09.930 に答える