source: src/cor/corr.cc

Last change on this file was 5f4d9c3, checked in by Maciej Prill <mprill@…>, 13 years ago

Rewritten the build system, added lem UTF-8 version.

  • Property mode set to 100644
File size: 2.7 KB
Line 
1//---------------------------------------------------------------------------
2
3#include "corr.hh"
4
5#define MAXPATH 256
6
7#define min(x,y) ((x<y)?(x):(y))
8#define max(x,y) ((x>y)?(x):(y))
9
10
11int Corr::ed(int i,int j)
12{
13  if(i==-1)
14    return j+1;
15  if(j==-1)
16    return i+1;
17  if(i==-2 || j==-2)
18    return n+1;
19
20  if(X[i]==Y[j])
21    return H2[i-1][j-1];
22  if(X[i-1]==Y[j] && X[i]==Y[j-1])
23    return 1+min(H2[i-2][j-2],min(H2[i][j-1],H2[i-1][j]));
24  return 1+min(H2[i-1][j-1],min(H2[i][j-1],H2[i-1][j]));
25
26/*
27  if(X[i]==Y[j])
28    return H[(i-1)+2][(j-1)+2];
29  if(X[i-1]==Y[j] && X[i]==Y[j-1])
30    return 1+min(H[(i-2)+2][(j-2)+2],min(H[(i)+2][(j-1)+2],H[(i-1)+2][(j)+2]));
31  return 1+min(H[(i-1)+2][(j-1)+2],min(H[(i)+2][(j-1)+2],H[(i-1)+2][(j)+2]));
32*/
33}
34
35int Corr::cuted(int j)
36{
37  int l=max(0,j-t);
38  int u=min(m,j+t);
39  int ce=j+t;
40  for(int k=l;k<=u;k++)
41  {
42    if(H2[k][j]<ce)//if(H[(k)+2][(j)+2]<ce)
43      ce=H2[k][j];//ce=H[(k)+2][(j)+2];
44  }
45  return ce;
46}
47
48/*
49void Corr::recomputeH(int j)
50{
51  for(int i=0;i<=m;i++)
52    H[(i)+2][(j)+2]=ed(i,j);
53}
54*/
55
56void Corr::recomputeH(int j)
57{
58  int lo=max(0,j-t-2);
59  int hi=min(m,j+t+2);
60  for(int i=lo;i<=hi;++i)
61    H2[i][j]=ed(i,j);//H[(i)+2][(j)+2]=ed(i,j);
62}
63
64
65int Corr::correct(const char* w, Words& tab)
66{
67  long int path[MAXPATH]={0};
68  int i;                                    // row index (X)
69  int j;                                    // column index (Y)
70  long state=0;
71
72  strcpy(X,w);
73  m=strlen(X)-1;
74  n=m+t;
75
76  for(i=(-2);i<=m;i++)
77    H[(i)+2][(-2)+2]=n;
78  for(i=(-1);i<=m;i++)
79    H[(i)+2][(-1)+2]=(i)+1;
80  for(j=(-2);j<=n;j++)
81    H[(-2)+2][(j)+2]=n;
82  for(j=(-1);j<=n;j++)
83    H[(-1)+2][(j)+2]=(j)+1;
84
85  for(j=0; j<=n; ++j)
86    for(i=0; i<=m; ++i)
87      H[i+2][j+2]=t+1;
88
89  int more=1;
90  bool cont=false;
91
92  strcpy(Y,"");
93  j=0;
94  state=0;
95  int count=0;
96  while(more)
97  {
98    if(!empty(state))
99    {
100      Y[j]=input(state);
101      recomputeH(j);
102      if(cuted(j)<=t)
103      {
104        int edd;
105        if(final(next(state)) && (edd=H[(m)+2][(j)+2])<=t)
106        {
107          char* out=new char[j+2];
108          strncpy(out,Y,j+1);
109          out[j+1]='\0';
110          //          if(cont) putchar(' ');
111          cont=true;
112          //          printf("%i,%s", edd,out);
113          //          cout << out << "(" << edd << ")" << endl;
114          tab.add(out);
115          count++;
116        }
117        path[j++]=state;
118        state=next(state);
119        continue;
120      }
121      else
122        if(continued(state))
123        {
124          state++;
125          continue;
126        }
127    }
128    //backtracking
129    do
130      if(j>0)
131        j--;
132      else
133        more=0;
134    while(more && !continued(path[j]));
135    state=path[j]+1;
136  }
137  return count;
138}
139
140
141//---------------------------------------------------------------------------
142
Note: See TracBrowser for help on using the repository browser.