Расстояние Левенштейна

Тема в разделе "Базы данных", создана пользователем @lex, 12 ноя 2010.

Статус темы:
Закрыта.
Модераторы: latteo
  1. @lex

    @lex Постоялец

    Регистр.:
    13 июн 2006
    Сообщения:
    50
    Симпатии:
    3
    Как в MySQL реализовать расчет расстояния Левенштейна между значениями колонки? Задача: из списка названий нечетко найти самое популярное.
     
  2. Sammerset

    Sammerset Постоялец

    Регистр.:
    14 сен 2008
    Сообщения:
    136
    Симпатии:
    10
    Написать пхп скрипт и рассчитывать. Поподробнее, что надо искать, какие колонки, сколько колонок - мясо, мясо давай!
     
  3. @lex

    @lex Постоялец

    Регистр.:
    13 июн 2006
    Сообщения:
    50
    Симпатии:
    3
    Хочется сделать процедуру для mysql.

    На php это сейчас реализовано так:

    Колонка 1. Строк в таблице 9 000 000. После группировки остается около 1500, из них для каждой по ~10 названий. Из этих 10 названий нужно сделать 1

    PHP:
    ....
    $in 'Название 115257 наш,Мой Название 115257,Названиечко 1152, ...   ,Название 115257';
        private function 
    chooseName($in) {
            if (!
    is_array($in)) {
                
    $in explode(','$in);
            }
            
    $clean_in preg_replace('|[^a-zA-Z0-9а-яА-Я]+|u'''$in);
            
    $k count($clean_in);
            
    $out = array();
            for (
    $i 0$i $k$i++) {
                
    $min_lev 255;
                
    //$lev = array();
                
    for ($j 0$j $k$j++) {
                    if (
    $i != $j || $clean_in[$i] != $clean_in[$j]) {
                            
    $lev levenshtein($clean_in[$i], $clean_in[$j]);
                        if (
    $min_lev $lev) {
                            
    $min_lev $lev;
                        }
                    }
                }
                
    $out[] = array($min_levstrlen($in[$i]), $i);
            }
            
    usort($out, array('Controller''cmp'));
            return 
    $in[$out[0][2]];
        }

        private function 
    cmp($a$b) {
            if (
    $a[0] == $b[0]) {
                if (
    $a[1] == $b[1]) {
                    return 
    0;
                } else {
                    return (
    $a[1] < $b[1]) ? : -1;
                }
            } else {
                return (
    $a[0] > $b[0]) ? : -1;
            }
        }
    ....
    Мясо дано, нужны угли, мангал и шампуры :)


    Расстояние Левинштейна для MySQL:

    PHP:
    CREATE FUNCTION levenshteins1 VARCHAR(255), s2 VARCHAR(255) )
      
    RETURNS INT
      DETERMINISTIC
      BEGIN
        
    DECLARE s1_lens2_lenijcc_tempcost INT;
        DECLARE 
    s1_char CHAR;
        DECLARE 
    cv0cv1 VARBINARY(256);
        
    SET s1_len CHAR_LENGTH(s1), s2_len CHAR_LENGTH(s2), cv1 0x00110;
        IF 
    s1 s2 THEN
          
    RETURN 0;
        ELSEIF 
    s1_len 0 THEN
          
    RETURN s2_len;
        ELSEIF 
    s2_len 0 THEN
          
    RETURN s1_len;
        ELSE
          WHILE 
    <= s2_len DO
            
    SET cv1 CONCAT(cv1UNHEX(HEX(j))), 1;
          
    END WHILE;
          WHILE 
    <= s1_len DO
            
    SET s1_char SUBSTRING(s1i1), icv0 UNHEX(HEX(i)), 1;
            WHILE 
    <= s2_len DO
              
    SET c 1;
              IF 
    s1_char SUBSTRING(s2j1THEN 
                SET cost 
    0; ELSE SET cost 1;
              
    END IF;
              
    SET c_temp CONV(HEX(SUBSTRING(cv1j1)), 1610) + cost;
              IF 
    c_temp THEN SET c c_tempEND IF;
                
    SET c_temp CONV(HEX(SUBSTRING(cv1j+11)), 1610) + 1;
                IF 
    c_temp THEN 
                  SET c 
    c_temp
                
    END IF;
                
    SET cv0 CONCAT(cv0UNHEX(HEX(c))), 1;
            
    END WHILE;
            
    SET cv1 cv01;
          
    END WHILE;
        
    END IF;
        RETURN 
    c;
    END;

    CREATE FUNCTION levenshtein_ratios1 VARCHAR(255), s2 VARCHAR(255) )
      
    RETURNS INT
      DETERMINISTIC
      BEGIN
        
    DECLARE s1_lens2_lenmax_len INT;
        
    SET s1_len LENGTH(s1), s2_len LENGTH(s2);
        IF 
    s1_len s2_len THEN 
          SET max_len 
    s1_len
        ELSE 
          
    SET max_len s2_len
        
    END IF;
        RETURN 
    ROUND((LEVENSHTEIN(s1s2) / max_len) * 100);
    END;

    Но как ее применить для нахождения наиболее вероятного Названия?
     
    Flock нравится это.
  4. Sammerset

    Sammerset Постоялец

    Регистр.:
    14 сен 2008
    Сообщения:
    136
    Симпатии:
    10
    В смысле необходимо указать самое частое название строки?
     
  5. @lex

    @lex Постоялец

    Регистр.:
    13 июн 2006
    Сообщения:
    50
    Симпатии:
    3
    да, нечеткое
     
  6. Sammerset

    Sammerset Постоялец

    Регистр.:
    14 сен 2008
    Сообщения:
    136
    Симпатии:
    10
    ещё вопросик уточню - тебе на пыхе писать?
     
  7. @lex

    @lex Постоялец

    Регистр.:
    13 июн 2006
    Сообщения:
    50
    Симпатии:
    3
    В идеале хочется получить функцию mysql, у которой на входе список Названий через разделитель, на выходе самое вероятное Название.
     
  8. Sammerset

    Sammerset Постоялец

    Регистр.:
    14 сен 2008
    Сообщения:
    136
    Симпатии:
    10
    Осталось написать еще одну функцию, которая будет выбирать все записи, а затем в цикле по всем этим записям вызывать сравнение строк. Можно это реализовать на пыхе, а вышеприведённую функцию вызывать при вхождении в мускул.
     
Статус темы:
Закрыта.