Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: помогите найти теорию по алг. Оливера. similar_text()

 PHP.SU

 Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (1): [1]   

> Без описания
Поиск в теме | Версия для печати
dimonx3
Отправлено: 18 Мая, 2012 - 18:27:23
Post Id



Новичок


Покинул форум
Сообщений всего: 21
Дата рег-ции: Июнь 2010  


Помог: 1 раз(а)
ребята. помогите найти хоть какую-то теорию по алгоритму Оливера. он используется в функции similar_text(). в мануале вообще голяк. в книжке Core PHP Programing в описании этой функции тоже понты, но есть ссылка на книжку Programming Classics: Implementing the World's Best Algorithms http://www[dot]amazon[dot]com/Programmin[dot][dot][dot]ms/dp/0131004131 . погуглив эту книжку нигде так и не нашел где бы ее можно было скачать. везде только зарубежные сайты типа amazon, google books и т.д
в сорцах php вот что:
CODE (htmlphp):
скопировать код в буфер обмена
  1.  
  2. /* {{{ proto int similar_text(string str1, string str2 [, float percent])
  3.    Calculates the similarity between two strings */
  4. PHP_FUNCTION(similar_text)
  5. {
  6.         char *t1, *t2;
  7.         zval **percent = NULL;
  8.         int ac = ZEND_NUM_ARGS();
  9.         int sim;
  10.         int t1_len, t2_len;
  11.  
  12.         if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z", &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {
  13.                 return;
  14.         }
  15.  
  16.         if (ac > 2) {
  17.                 convert_to_double_ex(percent);
  18.         }
  19.  
  20.         if (t1_len + t2_len == 0) {
  21.                 if (ac > 2) {
  22.                         Z_DVAL_PP(percent) = 0;
  23.                 }
  24.  
  25.                 RETURN_LONG(0);
  26.         }
  27.  
  28.         sim = php_similar_char(t1, t1_len, t2, t2_len);
  29.  
  30.         if (ac > 2) {
  31.                 Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
  32.         }
  33.         RETURN_LONG(sim);
  34. }
  35. /* }}} */
  36.  

еще нашел http://citeseerx[dot]ist[dot]psu[dot]edu/vie[dot][dot][dot]i=10[dot]1[dot]1[dot]52[dot]1476 , но мне кажется что это совсем не то.
мне хоть пару абзацев теории или хотя бы расскажите как она работает, а то вообще фигня получается

(Отредактировано автором: 18 Мая, 2012 - 18:32:01)

 
 Top
Мелкий Супермодератор
Отправлено: 18 Мая, 2012 - 18:49:55
Post Id



Активный участник


Покинул форум
Сообщений всего: 11926
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 618 раз(а)
Ну уж коль взялись копать в сырцах - копайте полностью. Ищите дальше функцию php_similar_char, её разбирайте. Остальное - только обвязка, проверка параметров.

Это довольно компактный рекурсивный алгоритм (ext/standard/string.c , чуть выше куска, что привели вы)
CODE (text):
скопировать код в буфер обмена
  1. /* {{{ php_similar_str
  2.  */
  3. static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
  4. {
  5.         char *p, *q;
  6.         char *end1 = (char *) txt1 + len1;
  7.         char *end2 = (char *) txt2 + len2;
  8.         int l;
  9.        
  10.         *max = 0;
  11.         for (p = (char *) txt1; p < end1; p++) {
  12.                 for (q = (char *) txt2; q < end2; q++) {
  13.                         for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
  14.                         if (l > *max) {
  15.                                 *max = l;
  16.                                 *pos1 = p - txt1;
  17.                                 *pos2 = q - txt2;
  18.                         }
  19.                 }
  20.         }
  21. }
  22. /* }}} */
  23.  
  24. /* {{{ php_similar_char
  25.  */
  26. static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
  27. {
  28.         int sum;
  29.         int pos1, pos2, max;
  30.  
  31.         php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);
  32.         if ((sum = max)) {
  33.                 if (pos1 && pos2) {
  34.                         sum += php_similar_char(txt1, pos1,
  35.                                                                         txt2, pos2);
  36.                 }
  37.                 if ((pos1 + max < len1) && (pos2 + max < len2)) {
  38.                         sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
  39.                                                                         txt2 + pos2 + max, len2 - pos2 - max);
  40.                 }
  41.         }
  42.  
  43.         return sum;
  44. }
  45. /* }}} */

Как он работает, впрочем, сходу не понял Ниндзя


-----
PostgreSQL DBA
 
 Top
dimonx3
Отправлено: 19 Мая, 2012 - 02:49:55
Post Id



Новичок


Покинул форум
Сообщений всего: 21
Дата рег-ции: Июнь 2010  


Помог: 1 раз(а)
код не сложный. но код это все равно не то. хотелось бы норм. описания. где еще можно поискать?
 
 Top
Поиск в теме | Версия для печати
Страниц (1): [1]
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Прочее »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
  



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB