c - トライとサフィックス ツリーの実装

Question

私は Tries と Suffix Trees を研究しており、同じものを実装したいと考えていました。最初に実装の構造と基本的な考え方についてのアイデアを得ることができるいくつかのリンクを共有してください。

含まれている場合、良い例はプラスになります。

C での実装。

Answer 1

C アルゴリズム ライブラリ( http://fragglet.github.io/c-algorithms/ ) は、C での Trie 実装を提供します。BSD スタイルのライセンスによるオープンソースです。

C でのサフィックス ツリーの実装は、https ://github.com/0xtonyxia/suffix-tree にあります。

それが役立つことを願っています。

Answer 2

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

typedef struct trie trie;
struct trie
{
       char key;
       trie *next,*children;
};

trie *newnode(char s)
{
     trie *t=(trie *)malloc(sizeof(trie));
     t->key=s;
     t->next=t->children=NULL;
}

void insert(trie **t,char *s,int start)
{if(s[start]=='\0')
                   {
                          *t=newnode('#');
                          return;
                   } 
                   if(*t==NULL)
                   {
                               *t=newnode(s[start]);
                               insert(&(*t)->children,s,start+1);
                   }       
                   if((*t)->key==s[start])
                   insert(&(*t)->children,s,start+1);
                   else
                   insert(&(*t)->next,s,start);
}


bool search(trie *t ,char *s,int start)
{


     if(t==NULL)
     return false;

     if(t->key=='#' && s[start]=='\0')
     return true;

     if(t->key!='#' && s[start]=='\0' || t->key=='#' && s[start]!='\0')
     return false;

     if(t->key==s[start])
     return search(t->children,s,start+1);

     else
     return search(t->next,s,start);

     return false;
}

/*void push(trie **t ,char *str)
{                        int i=0;
                         for(i=0;i<strlen(str);i++)
                         insert(t,str[i]);
}*/

main()
{     int i=0;

      trie *t=NULL;
      char ch='y';
      while(ch=='y')
      {             
                    {char str[20];
                    fflush(stdin);
                    printf("Enter the word ");
                    gets(str);


                    insert(&t,str,0);
                    }
                   // push(&t,str);
                    fflush(stdin);
                    printf("more y/n ::");
                    ch=getchar();
      }

      ch='y';
      while(ch=='y')
      {char str[20];
      fflush(stdin);
      printf("Enter the string you want to search::");
      gets(str);

      fflush(stdin);
      if(search(t,str,0))
      printf("Found");
      else
      printf("Not Found");

      printf("\n more y/n ::");
      scanf("%c",&ch);

      }

    getch();  

}

Answer 3

ここに、私が非常に役立つことがわかったリンクを示します。

接尾辞木に関する 6 時間の講義 (講義 3 ～ 講義 5) Google SCICOMP 講義 5 (最長共通部分文字列問題: O(n) 接尾辞木、接尾辞の並べ替え)

一般化されたサフィックス ツリーの実装 http://www.geeksforgeeks.org/generalized-suffix-tree-1/

接尾辞ツリーによる高速文字列検索 http://marknelson.us/1996/08/01/suffix-trees/

ウィキペディアで Ukkonen アルゴリズムを調べてください。注: 十分な評判が得られないため、2 つを超えるリンクを投稿することはできません。

Answer 4

#include <iostream>
#include <string.h>
using namespace std;
int high;
struct stnode
{
    stnode* ptr[27];
    int start;
    int end;
    stnode(int s,int e)
    {
        for (int i = 0; i < 27; ++i)
        {
            ptr[i]=NULL;
        }
        start=s;
        end=e;
    }
}*root=NULL;


stnode* fun(stnode* child,string str,int ind)
{
    int s=child->start;
    while(s<=child->end&&str.at(s)==str.at(ind))
        {
            s++;
            ind++;
        }
    if(s<=child->end)
    {
        child->ptr[str.at(ind)-'a']=new stnode(ind,high);
        if(str.at(s)=='$')
            child->ptr[26]=new stnode(s,child->end);
        else
            child->ptr[str.at(s)-'a']=new stnode(s,child->end);
        child->end=s-1;
        return child;
    }
    else
    {
        if(child->ptr[str.at(ind)-'a'])
        {
            child->ptr[str.at(ind)-'a']=fun(child->ptr[str.at(ind)-'a'],str,ind);
            return child;
        }
        else
        {
            child->ptr[str.at(ind)-'a']=new stnode(ind,high);
            return child;
        }
    }

}



stnode* create(stnode* root,string str,int ind)
{
    if(!root)
    {
        root=new stnode(ind,high);
        return root;
    }
    if(str.at(ind)=='$')
    {
        root->ptr[26]=new stnode(ind,high);
        return root;
    }
    if(!root->ptr[str.at(ind)-'a'])
    {
        root->ptr[str.at(ind)-'a']=new stnode(ind,high);
        return root;
    }
    root->ptr[str.at(ind)-'a']=fun(root->ptr[str.at(ind)-'a'],str,ind);
    return root;
}



void display(stnode* root,string str)
{
    if(!root)
        return;
    if(root->start!=-1)
    {
        for(int i=root->start;i<=root->end;i++)
        {
            cout<<str.at(i);
        }
        cout<<"\n";
    }
    for(int i=0;i<27;i++)
    {
        display(root->ptr[i],str);
    }
}


int main(int argc, char const *argv[])
{
    string str;
    cout<<"enter the string.\n";
    cin>>str;
    str=str+"$";
    high=str.length()-1;

    root=new stnode(-1,-1);

    for(int i=str.length()-1;i>=0;i--)
    {
        root=create(root,str,i);
        display(root,str);
        cout<<"\n\n\n";
    }

    return 0;
}