Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Поиск и получение подстроки одинаковой для двух и более строк / 6 сообщений из 6, страница 1 из 1
11.02.2006, 22:59
    #33539116
lightspeed
lightspeed
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск и получение подстроки одинаковой для двух и более строк
Приветствую тебя, All
Поиск и получение подстроки одинаковой для двух и более строк.
Известно, что подстрока одинаковая для всех строк - единственная одинаковая подстрока.
Ищу наименее затратный по процессорному времени (не по памяти) алгоритм.
Сделал в тупую, разбирая первую строку и проверяя каждую ее подстроку с другими строками. Не удовлетворяет производительность.
Можно-ли это сделать с помощью grep/egrep кода?
Пока, не могу ничего нормального придумать...
:(
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.02.2006, 19:49
    #33541943
Ksnk
Ksnk
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск и получение подстроки одинаковой для двух и более строк
Чистой воды идея :) Нужно дорабатывать напильником, проверять на границы и протч., но всяко лучше, чем простой перебор вариантов
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
$a="Just to say Hello world. and nothing more!";
$b="Oops! Hello world. rr and thats all";
// try to found
$x= 0 ; $y= 0  ; $xl=strlen($a)- 1 ; $yl=strlen($b)- 1 ;
$k=levenshtein($a,$b);
for($i= 0 ;($i< 6 ) && ($k> 1 );$i++) { // я боюсь отпускать ее больше :)
  while (TRUE) {
     $x++ ; $kcur=levenshtein(substr($a,$x,$xl-$x),
                              substr($b,$y,$yl-$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $x-- ; break ; }
  }
  while (TRUE) {
     $y++ ; $kcur=levenshtein(substr($a,$x,$xl-$x),
                              substr($b,$y,$yl-$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $y-- ; break ; }
  }
  while (TRUE) {
     $xl-- ; $kcur=levenshtein(substr($a,$x,$xl-$x),
                              substr($b,$y,$yl-$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $xl++ ; break ; }
  }
  while (TRUE) {
     $yl-- ; $kcur=levenshtein(substr($a,$x,$xl-$x),
                              substr($b,$y,$yl-$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $yl++ ; break ; }
  }
// let's substr common part's
  $sub = $x;
  while ($a{$x}==$b{$y}) {$x++;$y++;}
  $substr[]=substr($a,$sub,$x-$sub); 
}
echo substr($a,$x,$xl-$x)."<br>";
echo substr($b,$y,$yl-$y)."<br>";
echo $k."<br>";
print_r($substr);
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.02.2006, 20:19
    #33541986
Ksnk
Ksnk
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск и получение подстроки одинаковой для двух и более строк
После предварительной доработки напильником получилось примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
$a="Just to say Hello world. and nothing more!";
$b="Oops! Hello world. rr and that's all";
// try to found
$x=0; $y=0 ; $xl=strlen($a)-1; $yl=strlen($b)-1;
$substr=array();
$k=2;
while(($x<$xl)&&($y<$yl)&&($k>1)) {
  $k=levenshtein(substr($a,$x),substr($b,$y)) ;
  while ($x<$xl) {
     $x++ ; $kcur=levenshtein(substr($a,$x),
                              substr($b,$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $x-- ; break ; }
  }
  while ($y<$yl) {
     $y++ ; $kcur=levenshtein(substr($a,$x),
                              substr($b,$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $y-- ; break ; }
  }
// let's substr common part's
  $sub = 0;
  while ($a{$x+$sub}==$b{$y+$sub}) {$sub++;}
  if ($sub>0)
    $substr[]=array('ax'=>$x,'bx'=>$y,'len'=>$sub,
                    'field'=>substr($a,$x,$sub));
  $x+=$sub ;$y+=$sub;
}
echo "<pre>";
print_r($substr);
echo "</pre>";
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2006, 15:28
    #33543911
lightspeed
lightspeed
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск и получение подстроки одинаковой для двух и более строк
KsnkПосле предварительной доработки напильником получилось примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
$a="Just to say Hello world. and nothing more!";
$b="Oops! Hello world. rr and that's all";
// try to found
$x=0; $y=0 ; $xl=strlen($a)-1; $yl=strlen($b)-1;
$substr=array();
$k=2;
while(($x<$xl)&&($y<$yl)&&($k>1)) {
  $k=levenshtein(substr($a,$x),substr($b,$y)) ;
  while ($x<$xl) {
     $x++ ; $kcur=levenshtein(substr($a,$x),
                              substr($b,$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $x-- ; break ; }
  }
  while ($y<$yl) {
     $y++ ; $kcur=levenshtein(substr($a,$x),
                              substr($b,$y));
     if ($k>=$kcur) $k=$kcur  ;
     else { $y-- ; break ; }
  }
// let's substr common part's
  $sub = 0;
  while ($a{$x+$sub}==$b{$y+$sub}) {$sub++;}
  if ($sub>0)
    $substr[]=array('ax'=>$x,'bx'=>$y,'len'=>$sub,
                    'field'=>substr($a,$x,$sub));
  $x+=$sub ;$y+=$sub;
}
echo "<pre>";
print_r($substr);
echo "</pre>";


Алгоритмическим способом я делал.
:)
Но, не устраивает производительность.
Теперь сделал regexp'ом, код сократился, производительность увеличилась.
Вот код:
Код: plaintext
1.
if ("$str1 $str2 $str3" =~ /(?:^|\W)(\w+)\W.*(?<=\W)\ 1 (?:\W|$)/) { $newest_string = $ 1 ; }

Сейчас задумался о построении некоторой модели, которая используя алгоритм Ахо-Корасика, строила-бы таблицу совпадающих слов.
Т.е., по вертикали совпадающие слова, по горизонтали - количество совпадений, для каждого слова.
Что имеем в результате. Имея по каждому документу данную таблицу, мы можем сравнивать слова со словами в строке поиска (предварительно обработав их лексически), и выдавать в результате документы, с некой статистической оценкой данного документа. При чем, чем выше эта оченка, тем ранее выдается документ. Как в гугле.
Таблица для каждого документа статична, и изменяется, если только дата изменения документа становится более современной. Т.е. функционал поиска опирается не на динамический поиск в документах, а на статический поиск в словарных таблицах. Скорость значительно выше. Да, и результаты поиска более интеллектуальные.
Вот такая задумка. Кстати, может кто уже такое делал?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2006, 15:53
    #33544023
Ksnk
Ksnk
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск и получение подстроки одинаковой для двух и более строк
Что-то мне указывает, что может пригодится full text search для мускула.

Правильно ли я понимаю, что предыдущая задача - "найти максимально большую общую часть двух строк" уже не очень актуальна? :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2006, 16:19
    #33544150
lightspeed
lightspeed
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск и получение подстроки одинаковой для двух и более строк
KsnkЧто-то мне указывает, что может пригодится full text search для мускула.

Правильно ли я понимаю, что предыдущая задача - "найти максимально большую общую часть двух строк" уже не очень актуальна? :)

Правильно. Т.к. на данный момент она уже работает.
Теперь идем далее.

И конечно, это уже другая тема.
:-)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Поиск и получение подстроки одинаковой для двух и более строк / 6 сообщений из 6, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 402ms
Закрыть
start [/forum/topic.php?fid=23&mobile=1&tid=1476754]:
 0ms
get settings:
 6ms
get forum list:
 8ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 157ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 19ms
get tp. blocked users:
 1ms
others: 200ms
total:  402ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]