Поиск (НЕ с) подстановочных знаков внутри троичного дерева поиска

Question

Я хочу изменить рекурсивную функцию из библиотеки "троичного дерева поиска" ( sourceforge & http://code.google.com/p/ternary-search-tree/). Поведение по умолчанию - искать в троичном дереве поиска все вхождения строк, которые соответствуют заданной подстановочной строке. т. е. наличие в дереве "KEY", "KE1", "KE2" позволило бы найти все записи, если я буду искать "KE*". Но мне нужно противоположное поведение - искать в троичном дереве поиска (которое содержит символы подстановки) все записи, которые соответствуют указанной строке. т. е. наличие в дереве "KE*", "KEY", "K*" должно найти все записи, если я ищу "KEY".

Дерево / узел определяется следующим образом:

typedef struct TstNode {
    TstNode( char c ) : splitChar(c), left(0), right(0), mid(0){
    }
    char splitChar;
    TstTree left, right;
    union {
        TstTree mid;
        int index;
    };
} tstNode;

И функция с поведением по умолчанию:

template <class Object>
void TernarySearchTree<Object>::partialMatchSearch(TstTree tree, const char *key)
{
    if (!tree) return;

    // partial match left
    if (*key == '?' || *key == '*' || *key < tree->splitChar)
    {
        partialMatchSearch( tree->left, key );
    }
    // partial match middle
    if (*key == '?' || *key == '*' || *key == tree->splitChar)
    {
        if ( tree->splitChar && *key )
        {
            if ( *key == '*' )
            {
                partialMatchSearch( tree->mid, key );
            }
            else
            {
                partialMatchSearch( tree->mid, key+1 ); // search next pattern char
            }
        }
    }
    if ( ( *key == 0 ||  *key == '*' ) && tree->splitChar == 0 )
    {
        pmVectorPtr->add( tree->index );
    }

    if (*key == '?' || *key == '*' || *key > tree->splitChar)
    {
        partialMatchSearch( tree->right, key );
    }
}

pmVectorPtr - это указатель на вектор целых чисел, и функция get вызывается с корневым элементом и поисковым ключом в качестве аргумента. Я уже пытался приспособиться к этому, но пока не могу разобраться. Мой собственный код:

template <class Object>
void TernarySearchTree<Object>::partialMatchSearchInverted(TstTree tree, const char *key)
{
    if (!tree) return;

    if((tree->splitChar == '*') && ( *key != 0 )){
        partialMatchSearchInverted( tree, key+1 );
    }

    if( *key != 0 ){
        if (*key < tree->splitChar){
            partialMatchSearchInverted( tree->left, key );
        }
        if (*key > tree->splitChar){
            partialMatchSearchInverted( tree->right, key );
        }
    }
    if ((*key == tree->splitChar) || (tree->splitChar == '*')){
        if ( tree->splitChar || *key ){
            partialMatchSearchInverted( tree->mid, key+1 ); // search next pattern char
        }
    }
    if ( ( *key == 0 ) && ( tree->splitChar == 0 ) ){
        pmVectorPtr->add( tree->index );
    }
}

Я закодировал это с широким использованием отладчика, и, насколько я могу судить, он "кажется" работает (даже если подстановочный знак находится в начале или в середине строки). НО, если я добавлю к примеру: "K*" и "Ke*" к дереву, он найдет только одно решение (в данном случае Ke*) для "Key". Если я удаляю "Ke*" из дерева, он находит "K*" для поискового запроса "Key". Я до сих пор не понимаю, почему.

Есть идеи по этому поводу?

---

Приложение (мой тестовый пример):

#include <iostream>
#include "ternarySearchTree/ternarySearchTree.h"

int main(int argc, char *argv[]){
    TernarySearchTree<string> tst;
    Vector< TstItem<String> > itemVector;
    {
        TstItem<String> item( "Ke*", "Value" );
        itemVector.add( item );
    }
    {
        TstItem<String> item( "K*", "Value" );
        itemVector.add( item );
    }
    {
        TstItem<String> item( "Ka*", "Value" );
        itemVector.add( item );
    }
    tst.buildBalancedTree(itemVector);

    Vector<int> matches = tst.partialMatchSearchInverted("Key");// will only find Ke* (wrong - it should find Ke* and K*), if I remove Ke* above it would find K* (right), if I remove that also it would find nothing (also right)
    for (unsigned j=0;j<matches.count();j++)
    {
        std::cout<<"Matching: "<< tst.getKey( matches[j] ) <<" -  "<< tst.getValue( matches[j] )->c_str()<<std::endl;
    }
    std::cout<<"total matches "<< matches.count()<<std::endl;
    return 0;
}

Answer 1

Хорошо, я наконец смог отследить свою проблему: я до сих пор не понял, как именно работает троичное дерево. Из-за этого я не посещал левый и правый узлы, когда где-то внутри этих ветвей мог быть подстановочный знак (к сожалению, это почти каждый раз). Так что мой последний алгоритм НАМНОГО медленнее, чем вообще должен быть поиск в троичном дереве (боюсь, сложность, вероятно, будет чем-то вроде O(n)), но, по крайней мере, я заставил его работать.

Таким образом, кажется, что эта структура данных не подходит для моих нужд (поиск подстановочных строк) - я, вероятно, получу ту же скорость с линейным списком. Однако, если кто-то с похожими проблемами когда-нибудь найдет этот вопрос, вот мой код (но я не предлагаю использовать его в реальных приложениях, потому что он медленный, и я предполагаю, что есть другие структуры вокруг, которые могут справиться с этими вещами намного лучше):

template <class Object>
void TernarySearchTree<Object>::partialMatchSearchInverted(TstTree tree, const char *key)
{
    if (!tree) return;
    if((tree->splitChar == '*') && ( *key != 0 )){
        partialMatchSearchInverted( tree, key+1 ); // wildcard occured, search same node with next key
    }
    if( *key != 0 ){
        if (*key < tree->splitChar){
            partialMatchSearchInverted( tree->left, key );
        }else if('*' < tree->splitChar){ // a wildcard could be in this branch
            partialMatchSearchInverted( tree->left, key );
        }
        if (*key > tree->splitChar){
            partialMatchSearchInverted( tree->right, key );
        }else if('*' > tree->splitChar){ // a wildcard could be here too
            partialMatchSearchInverted( tree->right, key );
        }
    }
    if ((*key == tree->splitChar) || (tree->splitChar == '*')){
        if (*key != 0){
            partialMatchSearchInverted( tree->mid, key+1 ); // search next pattern char
        }
    }
    if ( ( *key == 0 ) && ( tree->splitChar == 0 ) ){
        pmVectorPtr->add( tree->index );
    }
}