fork download
copy 
  1. #include <stdlib.h>
  2. #include <limits.h>
  3. #include <ctype.h>
  4. #include <string.h>
  5. #include <assert.h>
  6.  
  7. #include <stdio.h> /* nur für printf nötig */
  8.  
  9. #include <malloc.h> /* wegen alloca; nicht C-Standard! */
  10.  
  11. /*** mysql Zeugs, ohne das es hier nicht geht; muss natürlich wieder raus ***/
  12. #define UDF_INIT void
  13. typedef long longlong;
  14.  
  15. typedef struct {
  16. int arg_count;
  17. void **args;
  18. int *lengths;
  19. } UDF_ARGS;
  20. /************************************************/
  21.  
  22.  
  23. longlong levenshtein_k_base(UDF_INIT *initid, char *str1, char *str2, int distance, char *is_null, char *error)
  24. {
  25.   char *s = str1;
  26.   char *t = str2;
  27.  
  28.   int n = (s == NULL) ? 0 : strlen(str1);
  29.   int m = (t == NULL) ? 0 : strlen(str2);
  30.  
  31.   //order the strings so that the first always has the minimum length l
  32.   if (n > m) {
  33.     int aux = n;
  34.     n = m;
  35.     m = aux;
  36.     char *auxs = s;
  37.     s = t;
  38.     t = auxs;
  39.   }
  40.  
  41.  // const int k = *((int*) distance);
  42.   const int k = (int) distance;
  43.  
  44.  
  45.  
  46.   const int ignore = k + 1; //lev dist between s and t is at least greater than k
  47.   const int r = m - n;
  48.  
  49.   if (0 == n)
  50.     return (m > k) ? ignore : m;
  51.   if (0 == m)
  52.     return (n > k) ? ignore : n;
  53.   if (r > k)
  54.     return ignore;
  55.  
  56.   const int lsize = (((k > m) ? m : k) - r) / 2; //left space for insertions
  57.   const int rsize = lsize + r; //right space for deletions, rsize >= lsize (rsize == lsize iff r == 0)
  58.   const int stripsize = lsize + rsize + 1; // + 1 for the diagonal cell
  59.   const int stripsizem1 = stripsize - 1; //see later, not to repeat calculations
  60.  
  61.   int d[2 * stripsize]; //Current and last rows
  62.   int currentrow;
  63.   int lastrow;
  64.  
  65.  
  66.   /* Initialization */
  67.  
  68.   //currentrow = 0
  69.   int i;
  70.   for (i = lsize; i < stripsize; i++) //start from diagonal cell
  71.     d[i] = i - lsize;
  72.  
  73.  
  74.   /* Recurrence */
  75.  
  76.   currentrow = stripsize;
  77.   lastrow = 0;
  78.  
  79.   //j index for virtual recurrence matrix, jv index for rows
  80.   //bl & br = left & right bounds for j
  81.   int j, jv, bl, br;
  82.   int im1 = 0, jm1;
  83.   int a, b, c, min; //for minimum function, coded directly here for maximum speed
  84.   for (i = 1; i <= n; i++) {
  85.  
  86.     //bl = max(i - lsize, 0), br = min(i + rsize, m)
  87.     bl = i - lsize;
  88.     if (bl < 0) {
  89.       jv = abs(bl); //no space for all allowed insertions
  90.       bl = 0;
  91.     }
  92.     else
  93.       jv = 0;
  94.     br = i + rsize;
  95.     if (br > m)
  96.       br = m;
  97.  
  98.     jm1 = bl - 1;
  99.     for (j = bl; j <= br; j++) {
  100.       if (0 == j) //postponed part of initialization
  101.       d[currentrow + jv] = i;
  102.       else {
  103. 	//By observation 3, the indices change for the lastrow (always +1)
  104.   	if (s[im1] == t[jm1]) {
  105.   	  d[currentrow + jv] = d[lastrow + jv];
  106. 	}
  107.   	else {
  108. 	  //get the minimum of these 3 operations
  109. 	  a = (0 == jv) ? ignore : d[currentrow + jv - 1]; //deletion
  110. 	  b = (stripsizem1 == jv) ? ignore : d[lastrow + jv + 1]; //insertion
  111. 	  c = d[lastrow + jv]; //substitution
  112.  
  113. 	  min = a;
  114. 	  if (b < min)
  115. 	    min = b;
  116. 	  if (c < min)
  117. 	    min = c;
  118.  
  119. 	  d[currentrow + jv] = min + 1;
  120.   	}
  121.       }
  122.       jv++;
  123.       jm1 = j;
  124.     }
  125.  
  126.     //obsv: the cost of a following diagonal never decreases
  127.     if (d[currentrow + lsize + r] > k)
  128.       return ignore;
  129.  
  130.     im1 = i;
  131.  
  132.     //swap
  133.     currentrow = currentrow ^ stripsize;
  134.     lastrow = lastrow ^ stripsize;
  135.   }
  136.  
  137.   //only here if levenhstein(s, t) <= k
  138.   return (longlong) d[lastrow + lsize + r]; //d[n, m] }
  139. }
  140.  
  141. longlong abweichung(UDF_INIT *initid,char *suche,char *in,const char *e,int distance,char *is_null,char *error)
  142. {
  143.   #define MINDESTLAENGE 4
  144.   int index = 0;
  145.   while( in!=e )  /* im zu durchsuchenden char-Array alle "Worte" durchsuchen, also z.B. "abcd" in "xyz\0qwer\0usw\0" */
  146.   {
  147.     assert( (printf("%s ? %s\n",suche,in),1) );   
  148.     if( strlen(suche)>=MINDESTLAENGE && strlen(in)>=MINDESTLAENGE )   /* nur ab MINDESTLAENGE Zeichen mit Levensthein vergleichen */
  149.     {
  150.         longlong tmp=levenshtein_k_base(initid,suche,in,distance,is_null,error);
  151.  
  152.         assert( tmp>=0 );  /* Code geht davon aus, dass keine neg. Werte geliefert werden */
  153.         if(tmp <= distance) 
  154.           return index; /* Suchwort gefunden - Index zurückgegeben */
  155.  
  156.     }
  157.     else { /* Wenn Wörter kleiner/gleich 3 Zeichen direkten Vergleich durchführen */
  158.         if (strcmp(suche,in) == 0) 
  159.           return index; /* Suchwort gefunden - Index zurückgegeben */     
  160.     }
  161.     in+=strlen(in)+1;
  162.     index++;
  163.   }
  164.   return -1; /* Suchwort wurde nie gefunden */
  165. }
  166.  
  167. longlong relevance(UDF_INIT *initid, UDF_ARGS *args, char *is_null, char *error)
  168. {
  169.  
  170.   /* Such-Array bilden z.B. "C Entwickler" => "c\0entwickler\0centwickler\0" */
  171.   char *s0=alloca(2+2*(args->lengths[0])),*c=s0?s0:(abort(),NULL),*e=c;  memcpy(c,args->args[0],args->lengths[0]);c[args->lengths[0]]=0;
  172.   while(*e) { *e=tolower((unsigned char)*e),e++;}
  173.   strcpy(++e,s0);  s0[strlen(s0)]=' ';
  174.   while(*e) {if(*e==' ') memmove(e,e+1,strlen(e)); ++e; } ++e;
  175.   c=s0;
  176.   while(*c) {if(*c==' ') *c=0; ++c;}
  177.  
  178.   /* FRAGE:
  179.      Diesen oberen Teil versteh ich einfach nicht. Ich würde gerne einbauen dass er den Suchstring nur zusammensetzt wenn jeder wort min 2 Zeichen hat.
  180.      Im Fall "C Entwickler" würde dann das zusammengesetze Wort "centwickler" nämlich durch die levenshtein immer einen treffer bei "entwickler" haben. 
  181.      
  182.      Beispiel Array:
  183.      "PHP Entwickler"
  184.      [0] = php, [1] = enwickler, [2] = phpentwickler
  185.      
  186.      "C Entwickler"
  187.      [0] = c, [1] = entwickler
  188.   */
  189.  
  190.   /***************************************************************************/
  191.  
  192.   /*
  193.   FRAGE:
  194.   Nachdem ich den oberen Teil nicht verstehe weiß ich nicht wie ich auf die Anzahl der Suchworte komme (anz_suchbegriffe dh unten hardkodiert gesetzt).
  195.   Ich brauche diese deshalb da ja jedes Suchwort gefunden werden muss
  196.   */
  197.   int anz_suchbegriffe = 2; 
  198.  
  199.   /* Inserattitel-Wörter durchsuchen und Ende, falls "beste" Übereinstimmung hier schon gefunden */
  200.  
  201.   c=s0; 
  202.   {
  203.     int treffer = 0;
  204.     int phrase = 0;
  205.     int index_old = -1; 
  206.  
  207.     char *s1=alloca(1+args->lengths[1]),*x=s1?s1:(abort(),NULL); memcpy(x,args->args[1],args->lengths[1]);x[args->lengths[1]]=0;
  208.     while(*x) *x=tolower((unsigned char)*x),x++;
  209.     x=s1;
  210.     while(*x) {if(*x==' ') *x=0; ++x;} ++x;
  211.     while( c!=e ) /* alle Such-Wörter durchlaufen */
  212.     {
  213.       longlong index =abweichung(initid,c,s1,x,*(int *) args->args[3],is_null,error);
  214.       /* Es wird die Stelle im Inserattitel benötigt da die Suchwörter für eine 100%ige Relevanz hintereinander stehen müssen */
  215.       if( index > -1) {
  216.         treffer++;
  217.  
  218.         if ((index-1) == index_old || (treffer == 1)) /* Phrase-Variable dann setzen wenn das aktuelle Wort unmittelbar hinter dem letzten gefunden wurde bzw beim ersten Treffer sowieso */
  219.            phrase = 1;
  220.         else
  221.            phrase = 0;
  222.  
  223.         index_old = index;   
  224.  
  225.         /*
  226.         FRAGE: 
  227.         Hier muss jetzt noch eingebaut werden, dass wenn der letzte Schleifendurchlauf erfolgt (dann wird ja das zusammengesetzte Wort (zB "CEntwickler") gegen den Inserattitel geprüft),
  228.         die Trefferanzahl natürlich nicht gleich der der maximalen Suchbegriffe entspricht sondern einfach die Funktion abbrechen kann.
  229.         Beispiel:
  230.         Begriff: "PHP Entwickler" Inserat: "PHP MySQL Entwickler" => Zwei Suchbegriffe - dh wenn zwei Treffer Relevanz von 75 zurückgeben
  231.         Begriff "Software Entwickler" Inserat: "Softwareentwickler" => Ist auch korrekt (Relevanz von 100)
  232.         */
  233.  
  234.         if (treffer == anz_suchbegriffe) {
  235.            if (phrase == 1)
  236.               return 100; /* Wenn alle Suchwörter im Titel gefunden werden und diese hinteinaner stehen (Phrase) dann Relevanz von 100  */
  237.            else
  238.               return 75; /* Es wurden zwar alle Suchwörter gefunden aber diese standen nicht hintereinander -> dh 75 */
  239.         }
  240.       }
  241.       else phrase = 0;
  242.  
  243.       c+=strlen(c)+1;
  244.     }
  245.   }
  246.  
  247.   /* Inserattext-Wörter durchsuchen - Phrasen */
  248.  
  249.   c=s0;
  250.   {
  251.     char suchbegriff[args->lengths[0]+1];
  252.     memcpy(suchbegriff,args->args[0],args->lengths[0]);
  253.     suchbegriff[args->lengths[0]] = '\0';
  254.  
  255.     char *s1=alloca(1+args->lengths[2]),*x=s1?s1:(abort(),NULL); memcpy(x,args->args[2],args->lengths[2]);x[args->lengths[2]]=0;
  256.     while(*x) *x=tolower((unsigned char)*x),x++;
  257.     x=s1;
  258.     while(*x) {if(*x=='|') *x=0; ++x;} ++x;
  259.     longlong tmp=abweichung(initid,(char*) suchbegriff,s1,x,*(int *) args->args[3],is_null,error); 
  260.     if (tmp > -1)
  261.        return 75;
  262.   } 
  263.  
  264.  
  265.   /* Inserattext-Wörter durchsuchen */
  266.   c=s0;
  267.   {
  268.     int treffer = 0;
  269.     char *s1=alloca(1+args->lengths[2]),*x=s1?s1:(abort(),NULL); memcpy(x,args->args[2],args->lengths[2]);x[args->lengths[2]]=0;
  270.     while(*x) *x=tolower((unsigned char)*x),x++;
  271.     x=s1;
  272.     while(*x) {if(*x==' '||*x=='|') *x=0; ++x;} ++x;
  273.     while( c!=e )
  274.     {
  275.       longlong index=abweichung(initid,c,s1,x,*(int *) args->args[3],is_null,error);
  276.  
  277.       if (index > -1) {
  278.         treffer++;
  279.         if (anz_suchbegriffe == treffer) 
  280.            return 50;                   
  281.       }
  282.  
  283.       c+=strlen(c)+1;
  284.     }
  285.   }
  286.  
  287.   return 1; 
  288. }
  289.  
  290. int main()
  291. {
  292.   int i=1;
  293.   /*
  294.   Beispiele:
  295.   void *s[]={"php entwickler","php entwickler mysql","Software Entwickler|entwickler|Programmierer|php",&i}; => Relevanz 100
  296.   void *s[]={"php entwickler","phpentwickler mysql","Software Entwickler|entwickler|Programmierer|php",&i}; => Relevanz 100 (Derzeit nicht möglich!!!)
  297.   void *s[]={"php entwickler","php mysql entwickler","Software Entwickler|entwickler|Programmierer|php",&i}; => Relevanz 75 (Titel)
  298.   void *s[]={"php entwickler","php mysql developer","Software Entwickler|entwickler|Programmierer|php entwickler",&i}; => Relevanz 75 (Keyowords Phrasen)  
  299.   void *s[]={"php entwickler","Software Developer","Software Entwickler|entwickler|Programmierer|php",&i}; => Relevanz 50 (Keywords)
  300.   */
  301.   void *s[]={"php entwickler","Software Developer","Software Entwickler|entwickler|Programmierer|php",&i};
  302.   int l[]={14,18,48,0}; 
  303.   UDF_ARGS u={4,s,l};
  304.   printf("\n\nErgebnis: %ld \n",relevance(0,&u,0,0));
  305.   system("PAUSE");
  306.   return 0;
  307. }
  308.  
Success #stdin #stdout 0s 1844KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
php ? software
php ? developer
entwickler ? software
entwickler ? developer
phpentwickler ? software
phpentwickler ? developer
php entwickler ? software entwickler
php entwickler ? entwickler
php entwickler ? programmierer
php entwickler ? php
php ? software
php ? entwickler
php ? entwickler
php ? programmierer
php ? php
entwickler ? software
entwickler ? entwickler


Ergebnis: 50
https://ideone.com/Q89msn
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!