Оптимальный поиск и сравнение строк

[Utkin]

Имеется динамический массив не сортированных строк (их расположение имеет значение), строки длинные, их содержание и количество не важно и будут меняться. Собственно нужна скорость. Пишу на Дельфи, но меня прежде всего интересует алгоритм, поэтому пишу здесь. Какие будут варианты? Я сам думаю брать первый символ строки и искать сначала по нему, а уж потом проводить полное сравнение. Можно как вариант искать еще и по длине. Скажу сразу длина строк может быть любая и нуль и мегабайты.
Смысл затеи не добавлять дубликатов - массив должен содержать только уникальные строки.

[Alex Cones]

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

[VintProg]

//Функция нечеткого сравнения строк БЕЗ УЧЕТА РЕГИСТРА 

//------------------------------------------------------------------------------

//MaxMatching - максимальная длина подстроки (достаточно 3-4)

//strInputMatching - сравниваемая строка

//strInputStandart - строка-образец

 

// Сравнивание без учета регистра

// if IndistinctMatching(4, "поисковая строка", "оригинальная строка  - эталон") > 40 then ...

type

TRetCount = packed record

   lngSubRows: Word;

   lngCountLike: Word;

end;

 

//------------------------------------------------------------------------------

 

function Matching(StrInputA: WideString;

StrInputB: WideString;

lngLen: Integer): TRetCount;

var

TempRet: TRetCount;

PosStrB: Integer;

PosStrA: Integer;

StrA: WideString;

StrB: WideString;

StrTempA: WideString;

StrTempB: WideString;

begin

StrA := string(StrInputA);

StrB := string(StrInputB);

 

for PosStrA := 1 to Length(strA) - lngLen + 1 do

begin

   StrTempA := System.Copy(strA, PosStrA, lngLen);

 

   PosStrB := 1;

   for PosStrB := 1 to Length(strB) - lngLen + 1 do

   begin

     StrTempB := System.Copy(strB, PosStrB, lngLen);

     if SysUtils.AnsiCompareText(StrTempA, StrTempB) = 0 then

     begin

       Inc(TempRet.lngCountLike);

       break;

     end;

   end;

 

   Inc(TempRet.lngSubRows);

end; // PosStrA

 

Matching.lngCountLike := TempRet.lngCountLike;

Matching.lngSubRows := TempRet.lngSubRows;

end; { function }

 

//------------------------------------------------------------------------------

 

function IndistinctMatching(MaxMatching: Integer;

strInputMatching: WideString;

strInputStandart: WideString): Integer;

var

gret: TRetCount;

tret: TRetCount;

lngCurLen: Integer; //текущая длина подстроки

begin

   //если не передан какой-либо параметр, то выход

if (MaxMatching = 0) or (Length(strInputMatching) = 0) or

   (Length(strInputStandart) = 0) then

begin

   IndistinctMatching := 0;

   exit;

end;

 

gret.lngCountLike := 0;

gret.lngSubRows := 0;

   // Цикл прохода по длине сравниваемой фразы

for lngCurLen := 1 to MaxMatching do

begin

       //Сравниваем строку A со строкой B

   tret := Matching(strInputMatching, strInputStandart, lngCurLen);

   gret.lngCountLike := gret.lngCountLike + tret.lngCountLike;

   gret.lngSubRows := gret.lngSubRows + tret.lngSubRows;

       //Сравниваем строку B со строкой A

   tret := Matching(strInputStandart, strInputMatching, lngCurLen);

   gret.lngCountLike := gret.lngCountLike + tret.lngCountLike;

   gret.lngSubRows := gret.lngSubRows + tret.lngSubRows;

end;

 

if gret.lngSubRows = 0 then

begin

   IndistinctMatching := 0;

   exit;

end;

 

IndistinctMatching := Trunc((gret.lngCountLike / gret.lngSubRows) * 100);

end;

[Serge_Bliznykov]

а я бы рекомендовал посмотреть на решение проблемы с другой стороны - никто же не мешает завести динамический массив (или список/коллекцию - не суть важно) с номерами (индексами) строк и отсортировать его по значениям строк.
Тогда в этой структуре достаточно сравнивать соседние элементы (строки с этими индексами).

p.s. Предложенный выше алгоритм - это банальное индексирование данных.

p.p.s. а вообще, решение задачи ОЧЕНЬ сильно зависит от конкретных деталей (могут ли строки добавляться/удаляться, часто ли происходит изменение данных, какие требования к скорости (может банальнейший TSTringList + IndexOf по скорости устроит... ) и т.д. и т.п....

[BARNEY]

можно попробовать разделить разделись массив скажем на N и в N потоках сравнить.

Или этот масив строк скидывать в БД а там уже оптимальным запросом сравнивать. Сделать поле уникальным и БД сама будет это контролировать.

[Utkin]

Сообщение от Serge_Bliznykov

p.p.s. а вообще, решение задачи ОЧЕНЬ сильно зависит от конкретных деталей (могут ли строки добавляться/удаляться, часто ли происходит изменение данных, какие требования к скорости (может банальнейший TSTringList + IndexOf по скорости устроит... ) и т.д. и т.п....

Да, да и да, кроме TStringList'a. Строки могут и будут меняться, добавляться (планирую добавление в конец массива), удаляться и т.д. Именно поэтому сортировка не нравиться. Предполагаются активные изменения строк. Это будет что-то вроде умных указателей. Сам массив часть одной структуры, в которой чтобы не повторяться вместо строк будут храниться их индексы в данном массиве. Предполагается, что в данной структуре будут активные перемещения строк.

VintProg, я думаю мой вариант быстрей.

можно попробовать разделить разделись массив скажем на N и в N потоках сравнить.

Потоки не настоящий параллелизм. ИМХО, выгодно использовать для задач когда нужно выполнять разнотипные действия. В данном случае, скорость может быть даже ниже.

Насчет БД - это уже излишество. Задача сводиться к созданию определенной универсальной структуры данных. А если она еще и БД требовать начнет... Это не по-фень-шую.

[Пепел Феникса]

для начала строки какие?
Null Terminated или Lengthed?(или гибрид, как(вроде б) string)
если второе или третье то можно сначало длину сравнить, ну а затем POS проще будет я думаю(хотя на асме можно ускорить это...scasb/w(смотря какие строки))

[Utkin]

До 4-х гигабайт . Длинные.

[VintProg]

А размеры образца и самого текста могут отличатся???

[Utkin]

Сообщение от VintProg

А размеры образца и самого текста могут отличатся???

Да. В массиве могут храниться любые строки, включая пустую. Мне нужно поместить в этот же массив еще одну строку (тоже произвольную), но при условии, чтобы она уже не была добавлена в массив. Далее строки за ненадобностью будут удаляться из массива (из любого места). Далее строка может быть изменена (и нет никаких правил их изменения).