Проверка орфографии: троичное дерево поиска

Question

Я сделал код проверки орфографии, используя троичное дерево поиска. Кто-нибудь может сказать мне, как найти следующее возможное слово в TST. например, если я хочу найти, ищу ли я слово "мужественный" в средстве проверки правописания, а слово отсутствует в TST, поэтому вывод, который он выдает, имеет значение "ЗНАЧИТЕ ЛИ ВЫ": "Человек", "Манго"..значить можно рядом слова

Answer 1

Я реализовал свою собственную проверку орфографии, но вместо простого троичного дерева я использую троичный знак, как предлагает Питер Канковски. Вы можете посмотреть в моем блоге некоторые детали и как я это сделал. Это по-гречески, но вы можете понять.

Редактировать:

Хорошо вы правы Основная идея состоит в том, чтобы использовать предварительно созданный список кандидатов для заданного расстояния редактирования (для меня это значение 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++;
    }
}

После подготовки списка кандидатов, простой поиск в троичном переводе для каждого элемента в списке даст нам предложения для этого слова с ошибкой.

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

Примечание: словарь представляет собой скомпилированный (на основе файлов) троичный тег

Answer 2

Поиск слова в вашем TST закончится в определенном месте дерева. С этого момента вы можете просто подняться на один уровень вверх по дереву, пока не достигнете уровня, на котором есть нечто большее, чем просто ребенок, из которого вы пришли.

На этом уровне вы можете просто выбрать другие возможные пути и вернуть эти слова.