Форум "Проекты"

Проектирование - перед тем как писать код программы...

#0 Deep © 26.01.08 01:11:58 - 27.01.08 10:53:45

Свой поисковый сервер

Нет, я не собираюсь доганять и переганять Гугл и Яндекс.

Этот вопрос меня заинтересовал чуть-чуть с другой стороны. Но насколько я понимаю это напрямую связано с технологиями поисковых серверов. Допустим, есть база данных с анекдотами и афоризмами, которая допустим 5 лет наполнялась разными людьми. Отмодерировать эту базу вручную не представляется возможным (долго, нудно, дорого и т.п.). Нужно:

1)найти все дубли афоризмов и анекдотов (они могут незначительно отличаться словами, пунктуацией, регистром букв). Если это очень трудоемко для анекдотов, тогда будем считать, что это нужно сделать только для афоризмов (предложений из 10-30 слов). Интересует сам алгоритм, и конечно хочеться чтоб он был эффективным.

2)сделать автоматическую подвязку новых анекдотов к категориям (одной или нескольким, в зависимости от ключевых слов). Например, анекдот, который начинается словами "Сказали Вовочке, чтоб его отец пришел в школу..." должен попасть в разделы "Анекдоты про Вовочку", "Анекдоты про школу". При этом глупо указывать в ключевых словах "школа, школу, школе, ...". Наверное, нужно сразу обрезать до "школ", но тогда еще надо учитывать, что слово может быть первым в предложении и будет написано с большой буквы(Школа ...). Или же оно в анекдоте является акцентирующим и оно полность написано заглавными буквами (... ШКОЛА!).

Как в даном случае поступают поисковики? Я читал, что они работают с хеш-функциями для строк. Что-то наподобии этого:

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

Реализация функции soundex описана Дональдом Кнутом (Donald Knuth) в книге "The Art Of Computer Programming, vol. 3: Sorting And Searching", Addison-Wesley (1973), стр. 391-392.

Собственно, на этом моя теоретическая обознанность о возможных инструментальных средствах заканчивается.

И этого конечно очень мало, для того чтоб качественно реализовать задумку. Буду рад любым полезным советам, идеям, ссылкам.

#1 Мао Ля © 26.01.08 13:52:28

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

По поводу soundex:

В тему катологизации #100
имхо, тоже, эффективно задача может решаться только в рамках ИИ. Ну или, хотя бы, какая-то хитрая нейросеть.

По морфологическому разбору русского языка

#2 Deep © 26.01.08 15:00:27

> #1 Мао Ля ©
гм... нет, ИИ мне точно не нужен. Эта задача того не стоит. Нейросети - это конечно интересно, ведь далеко не просто. Морфологический разбор -- конечно хорошо, но наверное тоже лишнее. ИМХО, перед стравнеем достаточно "на глаз" отбрость окончания в "длинных" словах (существительных, прилагательных, глаголах) и сравнивать уже оставшиеся части строк.

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

Если исходный массив значений soundex совпадает на 70 (или 80/90, что определяется уже пользователем) и больше процентов, то можно предполагать, что эти строки несут примерно одинаковый смысл.

Итого, сравнение текстов можно привести к сравнению строковых 4-байтовых массивов (Пример массива: E324, D235, H456, A345). Какие есть идеи по сравниванию таких массивов? При этом нужно понимать, что A345 <> A346, но они практически равны (возможно, была опечатка или пропущена буква).

#3 Мао Ля © 26.01.08 15:48:31

На работе как раз столкнулись с задачей нечеткого сравнения строк - нужно искать дубли персон в базе по ФИО + паспортные данные. Вроде нашли простенький алгоритм ( ), переписали его на Java.. Но быстродействие оказалось удручающим.. И возникли такие проблемы, как, например, сравнение "Петров" и "Пертов" дает всего 53% схожести - это плохо. Думаю, стоит еще попробовать MetaPhoneRu (ссылка выше).

> ИМХО, перед стравнеем достаточно "на глаз" отбрость окончания в "длинных" словах (существительных, прилагательных, глаголах) и сравнивать уже оставшиеся части строк.

Это отчасти и есть морфологический разбор.
Как оно будет работать "на глаз" не знаю.. Надо поднимать учебники по русскому языку ))

На все вопросы можно ответить эмпирически - реализовать несколько алгоритмов и погонять их по твоей базе анекдотов.

> что эти строки несут примерно одинаковый смысл.

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

#4 Deep © 26.01.08 18:02:47

ага, задачка довольная востребованая, применя можно много где, было бы хорошее решение.

> И возникли такие проблемы, как, например, сравнение "Петров"
> и "Пертов" дает всего 53% схожести - это плохо.
у, это как-то совсем неправильно...

> переписали его на Java.. Но быстродействие оказалось удручающим..
это проблема Джавы или самого алгоритма?

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

а насчет смысла, это да - я немного погорячился

Хотя вероятность, что таких фраз как ты привел в примере будет много -- очень низкая

#5 Мао Ля © 26.01.08 19:08:51

Проблема в алгоритме. Он нифига не линейный. Ну и еще, конечно, объем базы... Около 50000 записей надо загрузить и сравнить с исходной :)

public class NoClearComparator
{
    public int compare(int maxMatching, String a, String b)
    {
        if (maxMatching == 0 || a.length() == 0 || b.length() == 0)
            return 0;

        int lngCountLike = 0;
        int lngSubRows = 0;

        int[] tret;
        for (int i = 1; i < maxMatching; i++)
        {
            tret = matching(a, b, i);
            lngCountLike += tret[0];
            lngSubRows += tret[1];
            tret = matching(b, a, i);
            lngCountLike += tret[0];
            lngSubRows += tret[1];
        }
        if (lngSubRows == 0)
            return 0;

        return (int) (100.0 * (double) lngCountLike / (double) lngSubRows);
    }

    private static int[] matching(String a, String b, int width)
    {
        int countLike = 0;
        int subrows = 0;
        int alen = a.length() - width;
        int blen = b.length() - width;
        for (int i = 0; i <= alen; i++)
        {
            String tmpA = a.substring(i, i + width);
            for (int j = 0; j <= blen; j++)
            {
                String tmpB = b.substring(j, j + width);
                if (tmpA.equals(tmpB))
                {
                    countLike++;
                    break;
                }
            }
            subrows++;
        }
        return new int[]{countLike, subrows};
    }
}

#7 Мао Ля © 27.01.08 10:43:47

Нашел одну недоделку. Вместо
for (int i = 1; i < maxMatching; i++)
надо
for (int i = 1; i <= maxMatching; i++)
Но это сути не меняет.

#8 Мао Ля © 27.01.08 10:53:45

Блин, еще одна недоделка - не надо учитывать регистр..
Короче, наверно пооптимизируем эту функцию и будем юзать. Лучше пока ничего не нашлось.

Написать ответ