API tools faq
paste
Advertisement
andrei_zene

Sp_Check.h

andrei_zene
Apr 8th, 2011
52
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.57 KB | None | 0 0
raw download clone embed print report
  1. /*#########################################################################
  2.  
  3. sp_check.h
  4.  
  5. This header takes care about spell-checking from Levenshtein distance to
  6. diacritics. This is one of the Dr.Text project headers.
  7. Written by Andrei Zene, 2010.
  8.  
  9. #########################################################################*/
  10.  
  11.  
  12. #define COPY_LETTER 0
  13. #define INF 32000
  14.  
  15. int DIACRITIC = 1;
  16. int DELETE_LETTER = 3;
  17. int INSERT_LETTER = 3;
  18. int REPLACE_LETTER = 4;
  19. int TWIDDLE_LETTERS = 3;
  20.  
  21. const TCHAR KEYBOARD_MAP[32][15] = {
  22.                 _T("aqwszăâ"), // a 0
  23.                 _T("bnhgvp"), // b 1
  24.                 _T("cxdfv"), // c 2
  25.                 _T("dserfcxt"), // d ..
  26.                 _T("ewsdr"), // e
  27.                 _T("fdrtgvc"), // f
  28.                 _T("gcftyzhbv"), // g
  29.                 _T("hgyzujnb"), // h
  30.                 _T("iuokjî"),  //i
  31.                 _T("juikmnh"), // j
  32.                 _T("kciolmj"), // k
  33.                 _T("lopkş"), // l
  34.                 _T("mnjk"), // m
  35.                 _T("nbhjm"), // n
  36.                 _T("oiklp"), // o
  37.                 _T("polăşb"), // p
  38.                 _T("qwsa"), // q
  39.                 _T("redft"),  //r
  40.                 _T("sşawedxzy"), // s
  41.                 _T("tţrfgzyd"), // t
  42.                 _T("uikjhzy"), // u
  43.                 _T("vbgfcw"), // v
  44.                 _T("wsaeqv"),  //w
  45.                 _T("xyzsdc"), //x
  46.                 _T("yztujhgxsa"), //y
  47.                 _T("yztujhgxsa"), //z
  48.                 _T("ăaâîţşp"), // ă
  49.                 _T("âî"), // â
  50.                 _T("îiâăţş"), // î
  51.                 _T("şţăpol"),// ş
  52.                 _T("ţşpăî"),// ţ
  53.                 _T("/")
  54. };
  55.  
  56. const TCHAR caps = _T('A'-'a');
  57.  
  58.  
  59. int is_letter(TCHAR letter)
  60. {
  61.     if(letter >= _T('a') && letter <= _T('z'))
  62.             return 1;
  63.     return 0;
  64. }
  65.  
  66. int is_diacritic(TCHAR letter, TCHAR special_char)
  67. {
  68.     if(
  69.         (letter == _T('ă')) || (letter == _T('ţ'))  ||
  70.         (letter == _T('ş')) || (letter == _T('î'))  ||
  71.         (letter == _T('â')) || (special_char != 0 && letter == special_char)
  72.        )
  73.             return 1;
  74.  
  75.     return 0;
  76. }
  77.  
  78.  
  79. int is_word(CString cuvant)
  80. {
  81.     int i;
  82.     for(i = 0; i < cuvant.GetLength(); i++)
  83.         if(i > 0) {
  84.             if(!::IsCharAlphaW(cuvant[i]) && !is_diacritic(cuvant[i],_T('-')))
  85.                 return 0;
  86.         }
  87.         else
  88.             if(!::IsCharAlphaW(cuvant[i]) && !is_diacritic(cuvant[i],0))
  89.                 return 0;
  90.     if(i != 0)
  91.         return 1;
  92.     else
  93.         return 0;
  94. }
  95.  
  96. int minimul(int a, int b, int c, int d, int e, int f, int &which)
  97. {
  98.     int minim = a; which = -1;
  99.     if(b < minim) {minim = b;which = 0;}
  100.     if(c < minim) {minim = c;which = 1;}
  101.     if(d < minim) {minim = d;which = 2;}
  102.     if(e < minim) {minim = e;which = 3;}
  103.     if(f < minim) {minim = f;which = 4;}
  104.     return minim;
  105. }
  106.  
  107. int minimul(int a, int b, int c, int d, int e, int f)
  108. {
  109.     int minim = a;
  110.     if(b < minim) minim = b;
  111.     if(c < minim) minim = c;
  112.     if(d < minim) minim = d;
  113.     if(e < minim) minim = e;
  114.     if(f < minim) minim = f;
  115.     return minim;
  116. }
  117.  
  118. int needs_diacritic(TCHAR a, TCHAR b)
  119. {
  120.     if((a == _T('a') && b == _T('ă')) || (a == _T('ă') && b == _T('a')))
  121.         return 1;
  122.     if((a == _T('a') && b == _T('â')) || (a == _T('â') && b == _T('a')))
  123.         return 1;
  124.     if((a == _T('i') && b == _T('î')) || (a == _T('î') && b == _T('i')))
  125.         return 1;
  126.     if((a == _T('i') && b == _T('â')) || (a == _T('î') && b == _T('â')))
  127.         return 1;
  128.     if((a == _T('s') && b == _T('ş')) || (a == _T('ş') && b == _T('s')))
  129.         return 1;
  130.     if((a == _T('t') && b == _T('ţ')) || (a == _T('ţ') && b == _T('t')))
  131.         return 1;
  132.     return 0;
  133. }
  134.  
  135. int Levenshtein(CString a, CString b, int MINIMUM_DISTANCE)
  136. {
  137.     int c[30][30], n = a.GetLength(), m = b.GetLength();
  138.     // initializarea matricei de costuri
  139.     c[0][0] = 0;
  140.     for(int i = 1; i <= m; i++)
  141.         c[0][i] = i*INSERT_LETTER;
  142.     for(int i = 1; i <= n; i++)
  143.         c[i][0] = i*DELETE_LETTER;
  144.  
  145.     //ne construim matricea de costuri
  146.     int c_copy, c_delete, c_insert, c_replace, c_twiddle, c_diacritic;
  147.     for(int i = 1; i <= n; i++)
  148.         for(int j = 1; j <= m; j++) {
  149.             if(minimul(c[i][j-1], c[i-1][j], c[i-1][j-1], INF, INF, INF) <= MINIMUM_DISTANCE) {
  150.                 c_copy = c_twiddle = c_diacritic = INF;
  151.                 if(a[i-1] == b[j-1])
  152.                     c_copy = COPY_LETTER + c[i-1][j-1];
  153.                 else if(needs_diacritic(a[i-1], b[j-1]))
  154.                         c_diacritic = DIACRITIC + c[i-1][j-1];
  155.                 c_delete = DELETE_LETTER + c[i-1][j];
  156.                 c_insert = INSERT_LETTER + c[i][j-1];
  157.                 c_replace = REPLACE_LETTER + c[i-1][j-1];
  158.  
  159.                 //the replace cost can be reduced if the letter with which we replace is close to the wrong letter on the keyboard
  160.                 if(c_copy == INF) {
  161.                     if(is_letter(a[i-1]))
  162.                         if(wcschr(KEYBOARD_MAP[a[i-1] - 97], b[j-1]))
  163.                             c_replace -= 1;
  164.                     if(is_diacritic(a[i-1],'-')) {
  165.                         int special_asci;
  166.                         if(a[i-1] == _T('ă')) special_asci = 26;
  167.                         if(a[i-1] == _T('â')) special_asci = 27;
  168.                         if(a[i-1] == _T('î')) special_asci = 28;
  169.                         if(a[i-1] == _T('ş')) special_asci = 29;
  170.                         if(a[i-1] == _T('ţ')) special_asci = 30;
  171.                         if(a[i-1] == _T('-')) special_asci = 31;
  172.                         if(wcschr(KEYBOARD_MAP[special_asci], b[j-1]))
  173.                             c_replace -= 1;
  174.                     }
  175.                 }
  176.                 if(i >= 2 && j >= 2 && a[i-2] == b[j-1] && a[i-1] == b[j-2])
  177.                     c_twiddle = TWIDDLE_LETTERS + c[i-2][j-2];
  178.                 c[i][j] = minimul(c_copy,  c_diacritic, c_delete, c_insert, c_replace, c_twiddle);
  179.             }
  180.             else
  181.                 c[i][j] = INF;
  182.         }
  183.     return c[n][m];
  184. }
  185.  
  186. void Levenshtein2(CString a, CString b, int UserStats[2][7])
  187. {
  188.     int Changes[30][30];
  189.     int c[30][30], n = a.GetLength(), m = b.GetLength();
  190.     // initializarea matricei de costuri
  191.     c[0][0] = 0;
  192.     for(int i = 1; i <= m; i++) {
  193.         c[0][i] = i*INSERT_LETTER;
  194.         Changes[0][i] = 2;
  195.     }
  196.     for(int i = 1; i <= n; i++) {
  197.         c[i][0] = i*DELETE_LETTER;
  198.         Changes[0][i] = 1;
  199.     }
  200.  
  201.     //ne construim matricea de costuri
  202.     int c_copy, c_delete, c_insert, c_replace, c_twiddle, c_diacritic;
  203.     for(int i = 1; i <= n; i++)
  204.         for(int j = 1; j <= m; j++) {
  205.             c_copy = c_twiddle = c_diacritic = INF;
  206.             if(a[i-1] == b[j-1])
  207.                 c_copy = COPY_LETTER + c[i-1][j-1];
  208.             else if(needs_diacritic(a[i-1], b[j-1]))
  209.                     c_diacritic = DIACRITIC + c[i-1][j-1];
  210.             c_delete = DELETE_LETTER + c[i-1][j];
  211.             c_insert = INSERT_LETTER + c[i][j-1];
  212.             c_replace = REPLACE_LETTER + c[i-1][j-1];
  213.  
  214.             //costul de inlocuire poate fi redus daca litera cu care inlocuim e apropiata pe tastatura de litera gresita
  215.             if(c_copy == INF) {
  216.                 if(is_letter(a[i-1]))
  217.                     if(wcschr(KEYBOARD_MAP[a[i-1] - 97], b[j-1]))
  218.                         c_replace -= 1;
  219.                 if(is_diacritic(a[i-1],'-')) {
  220.                     int special_asci;
  221.                     if(a[i-1] == _T('ă')) special_asci = 26;
  222.                     if(a[i-1] == _T('â')) special_asci = 27;
  223.                     if(a[i-1] == _T('î')) special_asci = 28;
  224.                     if(a[i-1] == _T('ş')) special_asci = 29;
  225.                     if(a[i-1] == _T('ţ')) special_asci = 30;
  226.                     if(a[i-1] == _T('-')) special_asci = 31;
  227.                     if(wcschr(KEYBOARD_MAP[special_asci], b[j-1]))
  228.                         c_replace -= 1;
  229.                 }
  230.             }
  231.             if(i >= 2 && j >= 2 && a[i-2] == b[j-1] && a[i-1] == b[j-2])
  232.                 c_twiddle = TWIDDLE_LETTERS + c[i-2][j-2];
  233.             c[i][j] = minimul(c_copy, c_diacritic, c_delete, c_insert, c_replace, c_twiddle, Changes[i][j]);
  234.         }
  235.  
  236.     //we determin the changes that were made and save them in UserStats
  237.     int Mistakes = 0;
  238.     int j, k;
  239.     j = n; k = m;
  240.     while(j >0 && k >0) {
  241.         if(Changes[j][k] != -1) Mistakes++;
  242.         if(Changes[j][k] == -1) {j--;k--;} //copy_letter
  243.         else if(Changes[j][k] == 0)  {j--;k--;UserStats[1][0]++;} //diacritic
  244.         else if(Changes[j][k] == 1)  {j--;UserStats[1][1]++;} //delete
  245.         else if(Changes[j][k] == 2)  {k--;UserStats[1][2]++;} //insert
  246.         else if(Changes[j][k] == 3)  {j--;k--;UserStats[1][3]++;} //replace
  247.         else if(Changes[j][k] == 4)  {j -= 2;k -= 2;UserStats[1][4]++;} //twiddle
  248.     }
  249.     UserStats[1][5] += Mistakes;
  250. }
  251.  
  252. void RefreshCosts(int UserStats[2][7])
  253. {
  254.     DIACRITIC = UserStats[0][0];
  255.     DELETE_LETTER = UserStats[0][1];
  256.     INSERT_LETTER = UserStats[0][2];
  257.     REPLACE_LETTER = UserStats[0][3];
  258.     TWIDDLE_LETTERS = UserStats[0][4];
  259. }
  260.  
  261. //changes Levenshtein costs for calculating distance based on the mistakes he founds in the document
  262. void ChangeCosts(int UserStats[2][7])
  263. {
  264.     float percentage_scores[5];
  265.     for(int i = 0; i <= 4; i++) {
  266.         percentage_scores[i] = float(UserStats[1][i]) / float(UserStats[1][5]);
  267.     //  if(i == 3) {//replace e caz special pt ca in levenshtein scadem un pct daca litera e apropiata
  268.             if(percentage_scores[i] -(1 - float(float(UserStats[0][i])/4)) >= 0.25)
  269.                 UserStats[0][i]--;
  270.             else
  271.                 if(percentage_scores[i] != 1 && UserStats[0][i] == 0) UserStats[0][i] = 1;
  272.                 else
  273.                     if(percentage_scores[i] - (1 - float(float(UserStats[0][i])/4)) < -0.25)
  274.                         UserStats[0][i]++;
  275.     }
  276.     /*  }
  277.         else {
  278.             if(percentage_scores[i] = 0)
  279.                 UserStats[0][i] = 4;
  280.             else
  281.                 if(percentage_scores[i] < 0.25)
  282.                     UserStats[0][i] = 3;
  283.                 else
  284.                     if(percentage_scores[i] < 0.5)
  285.                         UserStats[0][i] = 2;
  286.                     else
  287.                         if(percentage_scores[i] < 1)
  288.                             UserStats[0][i] = 1;
  289.                         else
  290.                             UserStats[0][i] = 0;
  291.         }
  292.     }*/
  293.     RefreshCosts(UserStats);
  294. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!