Увеличить скорость выполнения

← →
User (2010-04-06 22:02) [0]

Здравствуйте. Очень нужен совет опытных людей.
У меня имеется список строковых предложений (По 4-5 слов в среднем) загруженных в TStringList. Количество предложений около 50 тыс.

Пример предложений:
0. Товарищество с ограниченной ответственностью
1. Открытое Акционерное Общество
2. закрытое Акционерное Общество
и т.п.

При вводе пользователем определенного текста, например "Акционерное общество", система ищет данный текст по нашему списку, и сравнивает с помощью "специальной функции сравнения 2х текстов" на процент схожести. Если процент переваливает за (например 70%) текст из списка должен быть отображен.

Проблема в том, что поиск происходит очень долго, при явном сравнении текстов типа (Str = SL.String[i]) Поиск на много быстрее, но функция сравнения на процент схожести, единственная самая быстрая которую я нашел. Подскажите, как можно ускорить процесс поиска, может быть использование потоков? Если да, то если можно по подробнее. Спасибо.

Сама функция нечеткого сравнения, взято из http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1147

function CompareStrings(S1, S2: string; MatchCount: integer; out NCount: integer):integer; var i, j, Count_, Count: integer; S1_, S2_: String; function Flag:Boolean; begin Result:= false; if (i + Count_ <= Length(S1_))and(j + Count_ <= Length(S2_)) then if (UpCharRus(S1_[i+Count_]) = UpCharRus(S2_[j+Count_])) {and(S1[j+Count_] <> " ")} then Result:= true; end; begin Count:= 0; NCount:= 0; S1_:=S1; ReplaceAllStr(S1_, " ", ""); S2_:=S2; ReplaceAllStr(S2_, " ", ""); if (S1_ = "")or(S2_ = "") then begin Result:= 0; NCount:= 255; Exit; end; i:= 1; repeat j:= 1; repeat if (UpCharRus(S1_[i]) = UpCharRus(S2_[j])){and(S1[i] <> " ")} then begin Count_:= 1; while flag do Inc(Count_); i:= i + Count_ - 1; j:= j + Count_ - 1; if Count_ >= MatchCount then Count:= Count + Count_; end; inc(j) until j >= Length(S2_); inc(i) until i >= Length(S1_); if Length(S1_) < Length(S2_) then Count_:= Length(S1_) else Count_:= Length(S2_); Result:= Count; NCount:= Count_ - Count; end;

← →
User (2010-04-06 22:05) [1]

Забыл добавить, поиск по вхождению исключается, поиск должен быть именно "нечеткого сравнения"

← →
Харакири (2010-04-06 22:28) [2]

>Забыл добавить, поиск по вхождению исключается, поиск должен быть именно "нечеткого сравнения"

Смотрю, у тебя не только сравнение "нечеткое", но и все остальное - такое же нечеткое. Особенно постановка вопросов.
Тебе что надо-то: "нечеткое сравнение" или "увеличить скорость выполнения"?

>UpCharRus(), ReplaceAllStr

Что это такое? Что-то это не то. Совсем не то. Приведи код.

>Количество предложений около 50 тыс.

Как ты перебираешь список? Не хочешь ли ты сказать, что у тебя до 50 000 * 50 000 = 2 500 000 000 сравнений?

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

← →
Jeer © (2010-04-06 22:35) [3]

> User (06.04.10 22:02)

Т.е пройти курс [само]обучения по известным талмудам для тебя не хляет ?

← →
Дмитрий Белькевич (2010-04-06 22:50) [4]

> Как ты перебираешь список? Не хочешь ли ты сказать, что
> у тебя до 50 000 * 50 000 = 2 500 000 000 сравнений?

Ну почему же - юзер ввёл строку, сравнили с 50-ю тысячами образцов.

1. Перевести код в асм. Может дать некоторое ускорение.
2. Попробовать распараллелить на 5-10 потоков. Все сравниваемые строки предварительно делятся на 5-10 TStringList"ов, каждый TStringList считается своим потоком.
3. Идеальный вариант - это использовать не саму строку, но её "слепок" - хэш, либо какую-то свою функцию - резать строку как-то на буквы/слоги/слова, считать их количество, или еще как-то. Идея в том, что бы сравнивать не "сырые данные" - строки, а предварительно так подготовленные, что бы можно было сравнивать "слепки" строк обычным сравнением, что даст наибыстрейшее нечёткое сравнение.

С этим алгоритмом, думаю, существенного прироста добиться не удастся. Неалгоритмическое ускорение, если повезёт, даст ускорение на порядок, думаю, не больше.

← →
Jeer © (2010-04-06 23:17) [5]

> Неалгоритмическое ускорение, если повезёт, даст ускорение
> на порядок, думаю, не больше.

Типа, пошел к цыганке, она нагадала, ты скинул ей и все путем ?
***
Бляха-муха - я просто валяюсь в песке под пирамидами от таких вот "советчиков".

← →
Дмитрий Белькевич (2010-04-07 00:19) [6]

> Типа, пошел к цыганке, она нагадала, ты скинул ей и все
> путем ?

Типа как-то так, да.

← →
Дмитрий Белькевич (2010-04-07 00:32) [7]

Предлагайте, Jeer, свой метод.

И так... Морщины сокращаются на 34.56%...

← →
MsGuns © (2010-04-07 00:32) [8]

Самое правильное решение - положить все эти "стотыщпяцот" названий на какой-нибудь склсервер и привести его в порядок (по крайней мере избавиться от перестановок одинаковых слов и "разнокапитанистых" букав) - на "доске" сразу прояснится, гад буду :)

← →
MsGuns © (2010-04-07 00:38) [9]

Эх, а вот интересно, у меня есть программулька, которая в указанной таблице сканирует столбец (CHAR) и определяет те поля, в которых не все символы в русской, украинской или английской кодировке, т.е. смешанный.
Сравнение идет посимвольное.
Так вот , даже на миллионных таблицах время сканирования одного столбца не превышает нескольких минут.

← →
Игорь Шевченко © (2010-04-07 00:46) [10]

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

то есть,
Товарищество с ограниченной ответственностью => ТВРЩСТВСОГРНЧНОТВСТВНСТ
Открытое Акционерное Общество => ОТКРТАКЦНРНОБЩСТВ
далее - поиск подцепочек

Это первое, что пришло на ум из опыта решения проблемы поиска совпадения фамилий на авиабилетах (транлитерация по хитрым правилам) с реальными фамилиями на русском языке

← →
Дмитрий Белькевич (2010-04-07 00:47) [11]

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

Тут, думаю, проблема не в посимвольности. Если бы алгоритм только один раз пробегался по строке (как и в случае обычного сравнения), то всё бы работало быстро (даже если без индексов и посимвольно делать). Но алгоритм, как я себе представляю, делает множество обращений к каждому элементу сраниваемых строк.

← →
Дмитрий Белькевич (2010-04-07 00:52) [12]

> Это первое, что пришло на ум из опыта решения проблемы поиска
> совпадения фамилий на авиабилетах (транлитерация по хитрым
> правилам) с реальными фамилиями на русском языке

Интересно, насколько метод надёжен? У нас тоже эта проблема имеется.

← →
Дмитрий Белькевич (2010-04-07 00:54) [13]

Поиск цепочек возможен средствами базы? Или хитрый предрассчёт - занесение цепочек в базу, потом - выборка?

← →
Игорь Шевченко © (2010-04-07 01:03) [14]

Дмитрий Белькевич (07.04.10 00:52) [12]

> Интересно, насколько метод надёжен? У нас тоже эта проблема
> имеется.

Для нашей задачи хватило.

> Поиск цепочек возможен средствами базы? Или хитрый предрассчёт
> - занесение цепочек в базу, потом - выборка?

Нам был нужен не поиск подцепочек, а полное сравнение результатов применения операции мамбл-ванго к выбранным из базы данным. То есть, имелся поисковый реквизит, по которому выбиралось ограниченное количество фамилий, к ним применялась мамбл-ванго, к входной фамилии тоже применялась одноименная операция, а потом тупо сравнивалось - совпало/не совпало. Если не совпало - штраф :)

← →
User (2010-04-07 09:39) [15]

> >UpCharRus(), ReplaceAllStr
> Что это такое? Что-то это не то. Совсем не то. Приведи код.

Да, в этих моментах я подправил.
UpCharRus - это AnsiUpperCase
ReplaceAllStr - StringReplace(, " ", "", [rfReplaceAll]);

> Как ты перебираешь список? Не хочешь ли ты сказать, что
> у тебя до 50 000 * 50 000 = 2 500 000 000 сравнений?

Нет, в примере сравнений 50 тыс, один пробег по списку. Это пример, в реале список будет пополняться ежедневно.

> Самое правильное решение - положить все эти "стотыщпяцот"
> названий на какой-нибудь склсервер и привести его в порядок
> (по крайней мере избавиться от перестановок одинаковых слов
> и "разнокапитанистых" букав) - на "доске" сразу прояснится,
> гад буду :)

Вот это уже интересно. Ускорится ли поиск если я при занесении в список сразу буду названий приводить в порядок?

> Т.е пройти курс [само]обучения по известным талмудам для
> тебя не хляет ?

Ну посоветуйте хотя бы книжку, статью - что читать, кого читать. Не во всех ведь книгах найдешь нужное.

← →
User (2010-04-07 10:16) [16]

Все, решил проблему. При загрузке списка сразу привел к верхнему регистру все тексты, а из функции убрал приведение к верхнему регистру. Функция в разы стала работать быстрее. Всем спасибо.

> [16] User (07.04.10 10:16)

А что это, если не секрет? Локальный вариант гугла?
Средний словарный запас человека для повседневого общения - это около 3-5 тысяч слов.
50000 выражений с ежедневным пополнением - это запись потоков мыслей? 8-)
Я бы попробовал выделять из выражений слова без последних 3-4 букв и забить их их в справочник. Выражения записал бы индексами этих слов. И по ним уже искал. Разумеется в БД.

← →
User (2010-04-07 11:52) [18]

> А что это, если не секрет? Локальный вариант гугла?

Это, что-то вроде самодельного ПО Trados. "Translation Memory", когда переводчик переводит тексты предложений, затем уже переведенные тексты заносит в базу, в след. раз что бы заново одно и тоже не переводить, программа покажет варианты переводов из БД, по проценту схожести.

> [18] User (07.04.10 11:52)

А не получится как с кэшем браузера? Типа если он небольшой, то ускоряет, а если вырос бесконтрольно - тормозит.

← →
User (2010-04-07 14:12) [20]

> А не получится как с кэшем браузера? Типа если он небольшой,
> то ускоряет, а если вырос бесконтрольно - тормозит.

Возможно и получится. Сейчас пробую потоковое решение данной проблемы, при миллионе записей работает быстренько, дальше думаю нужно кидать в потоки.

> дальше думаю нужно кидать в потоки.

не нужно

Увеличить скорость выполнения Найти похожие ветки