1

我使用三元搜索树制作了拼写检查器代码。谁能告诉我如何在 TST 中找到下一个可能的单词。例如，如果我想在拼写检查器中搜索单词“Manly”并且 TST 中不存在该单词，那么它给出的输出类似于 DO YOU MEAN: "Man" "Mango" 。.表示可能的近词

4

2 回答 2

1

我已经实现了自己的拼写检查器，但我使用的是 Peter Kankowski在这里建议的三元 dag，而不是简单的三元树。您可以查看我的博客了解一些详细信息以及我是如何做到的。它是希腊语，但你可以得到一个想法。

编辑：

好吧，你是对的。基本思想是为给定的编辑距离使用预先创建的候选列表（对我来说值 2 是可以的）。要减小列表的大小，可以使用通配符。当然，这样的列表可以用不同的方式构建。我更喜欢这样的 for / while 循环（例如，对于两个替换的候选者）

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++;
    }
}

在准备好候选列表之后，在三元 dag 中对列表中的每个项目进行简单的搜索将为我们提供该拼写错误的单词的建议。

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 );
            }
        }
    }
}

注意：字典是编译的（基于文件的）三元 dag

于 2015-06-20T12:10:38.180 回答
0

在 TST 中对单词的搜索将在树中的特定位置终止。从这一点开始，你可以简单地在树上上一层，直到你到达一个不仅仅是你来自的孩子的层次。

在那个级别上，您可以简单地选择其他可能的路径并返回这些单词。

于 2015-03-19T13:07:09.930 回答