Mise en œuvre des Essais et des Suffixes

Question

J'ai étudié les Essais de Tries et de Suffixes et je voulais les mettre en œuvre. S'il vous plaît partager quelques liens où je peux avoir une idée sur la structure et l'idée de base de la mise en œuvre pour commencer.

Un bon exemple, s'il est inclus, serait un plus.

mise en œuvre en C.

Answer 1

Le C Algorithmes Library (http://fragglet.github.io/c-algorithms/) offre une Trie implementation in C. C'est open-source avec une licence de style BSD.

Une implémentation d'arbre suffixe C se trouve ici: https://github.com/0xtonyxia/suffix-tree

J'espère que cela aide.

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

Voici les liens que j'ai trouvés très utiles.

6 conférence heure sur les arbres de suffixe (Lecture 3 Lecture 5) Google SciComp Lecture 5 (le plus long problème de sous-chaîne commune: O (n) arbre suffixe, suffixes tri)

Généralisée Suffixe Arbre mise en œuvre http://www.geeksforgeeks.org/generalized-suffix-tree-1/

chaîne recherche rapide avec arbre suffixe http://marknelson.us/1996/08/01/suffix-trees/

Consulter algorithme Ukkonen sur wikipedia. Remarque: Impossible de publier plus de 2 liens ne sont pas assez de réputation. Duplication possible de [tentatives de mise en œuvre de la structure de données ......... Application - Dictionary ............] (http://stackoverflow.com/questions/)

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