0

「三分探索木」ライブラリ ( 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 は int の Vector への Pointer であり、関数 get は root-element と searchkey を引数として呼び出されます。私はすでにそれを適応させようとしましたが、まだ理解できていません。私自身のコード:

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*」を追加すると、「Key」のソリューション (この場合は Ke*) が 1 つしか見つかりません。ツリーから 'Ke*' を削除すると、'Key' の検索クエリに対して 'K*' が見つかります。理由はまだわかりません。

それについてのアイデアはありますか？

付録（私のテストケース）：

#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;
}
4

1 に答える 1

0

わかりました、ようやく問題を突き止めることができました。三分木がどのように機能するのか、まだまったく理解していませんでした。そのため、ワイルドカードがこれらのブランチ内のどこかにある可能性があるときは、左右のノードにアクセスしませんでした (悲しいことに、ほとんどの場合です)。したがって、私の最終的なアルゴリズムは、三分木での検索よりもはるかに遅くなります (複雑さはおそらく 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 );
    }
}
于 2012-11-29T16:09:14.407 に答える