0

私は現在、スペルチェッカーを作成するためにBK-Treeを実装しています。私が使用している辞書は非常に大きい（数百万語）ので、非効率性をまったく許容できません。しかし、私が書いたルックアップ関数（おそらくプログラム全体の中で最も重要な部分）をより良くすることができることを私は知っています。私は同じことに関していくつかの助けを見つけることを望んでいました。これが私が書いたルックアップです：

public int get(String query, int maxDistance)
{
    calculateLevenshteinDistance cld = new calculateLevenshteinDistance();
    int d = cld.calculate(root, query);
    int tempDistance=0;

    if(d==0)
        return 0;

    if(maxDistance==Integer.MAX_VALUE)
        maxDistance=d;

    int i = Math.max(d-maxDistance, 1);
    BKTree temp=null;

    for(;i<=maxDistance+d;i++)
    {
        temp=children.get(i);
        if(temp!=null)
        {
            tempDistance=temp.get(query, maxDistance);
        }
        if(maxDistance<tempDistance)
            maxDistance=tempDistance;
    }

    return maxDistance;
}

ループを不必要に何度も実行していること、および検索スペースをトリミングしてルックアップを高速化できることを知っています。どうすればいいのかよくわかりません。

4

1 に答える 1

1

少しビザンチンの場合、ループは一般的に正しいように見えます。ただし、(tempdistance/maxdistance を使用して) 停止条件を絞り込む試みは正しくありません。BK ツリーの構造では、現在のノードから dk から d+k までのレーベンシュタイン距離内にあるすべてのノードを探索する必要があります。結果なので、そのように剪定することはできません。

ツリーを探索しすぎていると思う理由は何ですか?

BK ツリーよりも効率的であるため、L evenshtein Automataに関する私のフォローアップ投稿が参考になるかもしれません。ただし、スペル チェッカーを作成する場合は、Favonius の提案に従い、この記事の作成方法を確認することをお勧めします。これは単純な文字列距離チェックよりもスペル修正に適しています。

于 2010-10-06T12:39:15.783 に答える