Форматирование результатов поиска aka Google

Igor aka TiGR · 4 Июн 2005

Форматирование результатов поиска aka Google

Поискал по форуму, сайту, FAQ, но ничего не нашёл, а задача ИМХО интересная и сложная. Суть в следующем: производится поиск по объёмистым документам. На страницу выводится, скажем, 10 штук результатов. Запросы соответствуют стандарту MySQL BOOLEAN FULLTEXT, т.е. могут использоваться кавычки, плюсы, минусы, знаки вопроса, звёздочки (поддерживать бы хотя бы это). Выводить полные тексты никто не станет, надо выводить фрагменты (скажем, не более 300 символов), и тут начинается самое интересное:

Если поисковое слово всего одно - всё просто: ищем первое вхождение, и выводим. Можно использовать что-то вроде:

PHP:

$maxlength = 300;
preg_match("/(^|\W).{0," . $maxlength/2 . "}$searchword{0," . $maxlength/2 . "}(\W|$)/i", $text, $matches);

Всё бы ничего, но уже тут начинаются первые проблемы. Если слово находится близко к началу текста, будет выведено не 300 символов, а всего ~170.

Ещё сложнее ситуация, если слов два (и более). Дело в том, что слова могут стоять в произвольном порядке. Если есть место, где они стоят рядом - надо вывести в первую очередь его.

Если слов совсем много (штук пять) - тут вообще дурдом.

Короче, как можно решить данную задачу?

Цель - выводить результат как в Google. Если вводишь пять слов, и на странице есть место где рядом стоят все пять слов - гугл покажет именно его. Более того, если слова находятся группами - три там, два тут - гугл выведет оба этих фрагмента, разделив их многоточием.

Равно как и если запрос состоит из двух слов возможны два варианта:
1. слова стоят в тексте рядом (расстояние меньше чем maxlengh), и можно вывести одним результатом.
2. слова разнесены по тексту. Нужно вывести два фрагмента, суммарной длиной не больше maxlength, в каждом из фрагментов стоит своё слово.

Также, хочется, чтобы это не был метод "грубой силы" - всё таки придётся обрабатывать по десять текстов за раз, а при большом наплыве посетителей это может стать сильно заметно.

Necromant · 4 Июн 2005

PHP:

$maxlength = 150;
preg_match("/.{0,$maxlength}$searchword.{0,$maxlength}/si", $text, $matches);

$maxlength = 150;
$swlength = 50;
$sw = array('some', 'some2')
preg_match("/.{0,$maxlength}".join(".{0,$swlength}", $sw).".{0,$maxlength}/si", $text, $matches);

Igor aka TiGR · 4 Июн 2005

Данный пример будет работать только в случае, если слова расоложены в порядке 'some', 'some2'. Задо если в тексте будет фраза 'some2 some' - он её не найдёт...

Necromant · 4 Июн 2005

PHP:

$maxlength = 150;
$swlength = 50;
$sw = array('some', 'some2')

preg_match("/((.{0,$maxlength}".join(".{0,$maxlength})|(.{0,$swlength}", $sw).".{0,$maxlength}))+/si", $text, $matches);

о как

Igor aka TiGR · 4 Июн 2005

А для пяти слов?

Necromant · 4 Июн 2005

а там масив хоть 100 слов

Igor aka TiGR · 8 Июн 2005

Всё равно не пойдёт - данный шаблон "поймает" текст длиной хоть десять килобайт... Был бы текст соответствующий, да и потом, данный шаблон может поймать несколько стоящих рядом слов some, а места где рядом стоят some и some2 - уже будут потом.

-~{}~ 19.05.06 03:28:

Задача таки была решена, уже давно. Просто что-то руки недоходили выложить решение. Короче, алгоритм был разбит на несколько:

1. Если окажется, что в тексте нет искомого слова (такое бывает), выводится начало текста.

2. Если в тексте присутствует всего одно слово поиска (одно - не значит в единственном экземпляре). Скрипт постарается выдернуть два фрагмент, содержащих искомое слово.

3. Если в тексте приустствует 2 слова - будет предпринята попытка вырвать единый фрагмент текста, содержащий оба слова. Иначе будут выведены два маленьких фрагмента, в каждом из которых присутствует искомое слово.

4. Если в тексте присутсвует больше двух слов - будет предпринята попытка вырвать фрагмент где содержатся все слова. Иначе - откат к сценарию 2.

С последним сценарием ещё стоит поработать, но на данный момент меня этот скрипт очень устраивает. Кстати, в коде в комментах есть описание альтернативного сценария 4 - если единого куска найти не удалось.

Вот и код:

PHP:

<?php

class searchTextExtractor {

    var $maxlength   =     300;
    var $searchwords = array();
    var $pregs       =       0;
    var $text        =      "";
    var $hellipsis   =   " &nbsp;<b>&hellip;</b>&nbsp; ";
    var $wordnumber  =       0;

    function searchTextExtractor() {
        //constructor
    }

    function extractText($text, $searchwords, $maxlength=null, $highlight = false,
        $hellipsis=null) {

        $this->text = $text;
        $this->searchwords = $searchwords;

        if ($maxlength) {
            $this->maxlength = $maxlength;
        }
        if ($hellipsis) {
            $this->hellipsis = $hellipsis;
        }

        if (strlen($this->text) < $this->maxlength * 1.15) {
            // if text is shorter than maxlength+15% then just return it all
            $results = $this->text;
        } else {

            $this->countWords();

            switch ($this->wordnumber) {
                case 0:
                    $results = $this->extractBegining();
                case 1:
                    $results = $this->extractSingleWord();
                case 2:
                    $results = $this->extractTwoWords();
                default:
                    $results = $this->extractManyWords();
            }
        }

        if ($highlight) {
            return $this->highlight($results);
        }

        return $results;
    }

    function countWords() {
        // checks what words REALLY meet in the text and counts em
        foreach ($this->searchwords as $id => $word) {
            if (!preg_match("/\b$word\b/i", $this->text)) {
                unset($this->searchwords[$id]);
            }
            $this->pregs++;
        }
        return $this->wordnumber = count($this->searchwords);
    }

    function extractBegining() {
        // return first $this->maxlength characters
        $this->pregs++;
        preg_match("/^(?:.{0,$this->maxlength}[\.;:,]|.{0,$this->maxlength}\b)/smi",
            $this->text, $matches);
        return $matches[0] . $this->hellipsis;
    }

    function extractSingleWord() {
        // finding first occurance of single word
        $word = reset($this->searchwords);
        $spacelength = round($this->maxlength/2);
        $this->pregs++;
        preg_match("/(\W|^).{0,$spacelength}\b$word\b.{0,$spacelength}(\W|$)/smi",
            $this->text, $matches);
        return ($matches[1] != "" ? $this->hellipsis : "")
            . $matches[0] . ($matches[2] != "" ? $this->hellipsis : "");
    }

    function extractTwoWords() {
        // using optimized logic to find chunk containing both search words
        // it should be much faster than using many words search logic
        $spacelength = round($this->maxlength / 2);
        $word1 = reset($this->searchwords);
        $word2 = next($this->searchwords);
        $this->pregs++;
        if (preg_match("/(\W|^)(?:\w+\W+){3,7}(?:$word1\b.{0,$spacelength}\b$word2|$word2\b.{0,$spacelength}\b$word1)\b.{0,$spacelength}(\W|$)/smi",
            $this->text, $matches)) {
            return ($matches[1] != "" ? $this->hellipsis : "")
                . $matches[0] . ($matches[2] != "" ? $this->hellipsis : "");
        } else {
            $spacelength = round($spacelength/2.5);
            preg_match("/(\W|^).{0,$spacelength}\b$word1\b.{0,$spacelength}(?=\W)/smi",
                $this->text, $matches);
            $matchedtext = ($matches[1] != "" ? $this->hellipsis : "")
                . $matches[0] . $this->hellipsis;
            preg_match("/(\W).{0,$spacelength}\b$word2\b.{0,$spacelength}(\W|$)/smi",
                $this->text, $matches);
            return $matchedtext . $matches[0] . ($matches[2] != "" ? $this->hellipsis : "");
        }
    }

    function extractManyWords() {
        // try to find single text chunk containing all search words.
        $spacelength = round($this->maxlength/($this->wordnumber-($this->wordnumber*.15)));

        $this->pregs++;
        if (preg_match_all("/(\s|^)(?:\w+\s+){3,7}(?:(?<=\b)(?:" . join("|",
            $this->searchwords)
            . ")(?=\b).{0,$spacelength}){{$this->wordnumber}}(\s|$)/smi",
            $this->text, $matches)) {
            $maxwords=0;
            foreach($matches[0] as $key => $match) {
                $foundwords=0;
                $this->pregs++;
                preg_match_all("/(?:\b)(?:" . join("|", $this->searchwords) . ")(?:\b)/i",
                    strtolower($match), $words);
                $wordcount = count(array_unique($words[0])) +
                    count($words[0]) / ($this->wordnumber*1.6);
                if ($wordcount > $maxwords) {
                    $maxwords = $wordcount;
                    $maxkey = $key;
                }
                if ($wordcount >= $this->wordnumber) {
                    return ($matches[1][$key] != "" ? $this->hellipsis : "")
                        . $match . ($matches[2][$key] != "" ? $this->hellipsis : "");
                }
            }
            // still here? okay, what was the maxwordcount per chunk?
            if ($maxwords > 1) {
                return ($matches[1][$maxkey] != "" ? $this->hellipsis : "")
                    . $matches[0][$maxkey]
                    . ($matches[2][$maxkey] != "" ? $this->hellipsis : "");
            }
        }
        // still here? Sadly, this means that single chunk was not found,
        // lets try to find two chunks containing as much words as possible
        // simpliest solution (should be fixed somehow later):

        // !!! Idea: do the following:
        // 1. Decrease maxlength twice
        // 2. Go through found chunks and try to find chunks containing several words.
        // 3. Try to get 2 chunks containing all words
        //    Or... 2 chunks containing maximum words.
        return $this->extractTwoWords();
    }

    function highlight($text) {
        return preg_replace("/(?<=\b)(" . implode('|', $this->searchwords) . ")(?=\b)/i",
            "<span class=search_highlight>\$1</span>", $text);
    }
}

?>

С удовольствием выслушаю предложения и критику.

-~{}~ 19.05.06 03:39:

Пример работы:

PHP:

$text = "Какой-то текст, из которого нужно вырвать слова. Правда при таком коротком тексте будет срабатывать единственный сценарий - вывод всего текста.";
$words = array("слова", "поискового", "запроса");
$extractor = new searchTextExtractor;
$chunk = $extractor->extractText($text, $words, 400, true);
// 400 здесь - это макс. количество символов
// true - включить подсветку найденых слов.
// оба параметра можно опустить.

-~{}~ 19.05.06 03:40:

Пример работы:

PHP:

$text = "Какой-то текст, из которого нужно вырвать слова. Правда при таком коротком тексте будет срабатывать единственный сценарий - вывод всего текста.";
$words = array("слова", "поискового", "запроса");
$extractor = new searchTextExtractor;
$chunk = $extractor->extractText($text, $words, 400, true);
// 400 здесь - это макс. количество символов
// true - включить подсветку найденых слов.
// оба параметра можно опустить.

-~{}~ 19.05.06 03:40:

Пример работы:

PHP:

$text = "Какой-то текст, из которого нужно вырвать слова. Правда при таком коротком тексте будет срабатывать единственный сценарий - вывод всего текста.";
$words = array("слова", "поискового", "запроса");
$extractor = new searchTextExtractor;
$chunk = $extractor->extractText($text, $words, 400, true);
// 400 здесь - это макс. количество символов
// true - включить подсветку найденых слов.
// оба параметра можно опустить.

apustilnic · 7 Дек 2009

В код смайл попал: =/

Beavis · 7 Дек 2009

apustilnic
этому смайлу уже 4.5 года

AmdY · 8 Дек 2009

а может ну нафиг эти регулярки и решить задачу с помощью обычных текстовых функций, находим позицию, считаем сколько отрезать слева и справа, где следующее-предыдущее вхождение? а то получается какой-то огромный класс на ровном месте.

упс, не заметил что кто-то поднял древнюю тему.

dimagolov · 8 Дек 2009

AmdY, тема середины 2005!! года

apustilnic · 9 Дек 2009

dimagolov
Тема древняя, но проблемы появились именно по данному классу, в связи с чем и решил написать тут.

С картинкой разобрался ). Но проблемы возникают с текстами в кодировке utf-8.

Может у кого-то есть аналогичный класс, нормально работающий с utf? Или более интересные решения, т.к. класс действительно работает довольно медленно.

AmdY · 9 Дек 2009

модификатор u пробовал?

apustilnic · 9 Дек 2009

Модификатор "u" пробовал.
Функцию strtolower менял на mb_strtolower. С настройками php.ini для mb_string-ов вроде тоже все в порядке.

Но проблемы все равно не решились. Точнее в данном случае класс для некоторых текстов вообще перестал генерировать выдержки - на выходе пусто.

А как на счет других готовых классов? Или это единственный? ))

dimagolov · 9 Дек 2009

apustilnic, http://phpfaq.ru/debug

apustilnic · 10 Дек 2009

dimagolov, Зачем же сразу пинать к FAQ-у?

Проблема то ведь проявляется с PCRE-функциями при обработке текстов в utf-8.

Покопал в эту сторону. Вот тут пишут, что для корректного использования, необходим не только указывать модификатор "u", но и заменять некоторые символьные классы, к примеру \w на их utf-аналоги:

http://blog.sjinks.pro/wordpress/patches/372-simple-tags-auto-link-tags-in-russian/

Здесь нашел таблицу этих самых "utf" заменителей
http://www.piter.com/attachment.php?barcode=978546900215&at=exc&n=0

Пока что не могу понять, чем можно заменить класс \W

У кого-нибудь есть более подробная инфа по данному вопросу?

Активист · 10 Дек 2009

Cфинкс нужно юзать))) там есть подсветка)))

apustilnic · 10 Дек 2009

Активист
Слышал про сфинкс, вещь хорошая.

Но в рамках поставленной мне задачи было необходимо написать несложный поиск на php+mySQL

Все собственно готово, осталось прикрутить лишь генерацию выдержки из текста. Вот тут то и попал в засаду.

Активист · 10 Дек 2009

apustilnic
А со сфинском еще меньше проблем)))

apustilnic · 11 Дек 2009

Вопрос вроде решился.

Для корректной работы нужно было лишь заменить \b перед словом на (?<!\pL), а \b после слова на (?!\pL)

Детали тут:
http://forum.dklab.ru/viewtopic.php?t=36043

Доработаю класс, предложенный Igor aka TiGR, и выложу его тут чуть позже.

Форматирование результатов поиска aka Google

Новичок

Новичок

Новичок

Новичок

Новичок

Новичок

Новичок

Новичок

Banned

Пью пиво

Новичок

Новичок

Пью пиво

Новичок

Новичок

Новичок

Активист

Новичок

Активист

Новичок