Алгоритм поиска Бойера-Мура-Хорспула
|
|
haav | Дата: Понедельник, 14.10.2024, 08:47 | Сообщение # 1 |
Генералиссимус
Группа: Администраторы
Сообщений: 1372
Статус: Offline
| Это алгоритм поиска Бойера-Мура-Хорспула для поиска подстроки в строке. Так же в коде есть небольшая процедура прямого поиска. Код написан мною для последующего его перевода на ASM , что и было потом сделано. Но поскольку код ASM здесь мало кому интересен , то выкладываю только код FB:
Код Function DirectSearch(_ start As Integer, _ pszBuf As Zstring Ptr,_ pszTemplate As Zstring Ptr,_ iLenBuf As Integer,_ iLenTemplate As Integer) As Integer
Dim As Integer iTemp For i As Integer = start-1 To iLenBuf-1 If (*pszBuf)[i] = (*pszTemplate)[iTemp] Then iTemp+=1 If iTemp >= iLenTemplate Then Return i - iLenTemplate +2 Endif Else iTemp = 0 Endif Next End Function
Function Search (iStart As Integer , pszBuf As Zstring Ptr, pszTemplate As Zstring Ptr , iLenBuf As Integer , iLenTemplate As Integer) As Integer Dim As Ubyte bTable(255) Dim As Integer iPointer = iLenTemplate - 1 + (iStart-1) Dim As Integer iPointerTemplate = iLenTemplate - 1 Dim As Integer iBackPointer = iPointer Dim As Integer iRet
For i As Integer = 0 To 255 bTable(i) = iLenTemplate Next Dim iDistance As Byte = 1 For i As Integer = iLenTemplate-2 To 0 Step -1 Dim bChar As Ubyte = (*pszTemplate)[i] If bTable(bChar) = iLenTemplate Then bTable(bChar) = iDistance Endif iDistance +=1 Next Do Dim As Ubyte bCharBuf = (*pszBuf)[iPointer] Dim As Ubyte bCharTemplate = (*pszTemplate)[iPointerTemplate] If bCharBuf = bCharTemplate Then iRet = iPointer+1 iPointer-=1 iPointerTemplate-=1 If iPointerTemplate < 0 Then Exit Do Endif Else Dim As Ubyte bChar = (*pszBuf)[iBackPointer] Dim As Integer iDistance = bTable(bChar) iPointerTemplate = iLenTemplate - 1 iPointer = iBackPointer + iDistance iBackPointer = iPointer iRet = 0 Endif If iPointer >= iLenBuf Then Exit Do Endif Loop Return iRet End Function
Dim As Zstring Ptr psz0 = @"Hello world" Dim As Zstring Ptr psz1 = @"ld"
? DirectSearch(1, psz0 , psz1 , Len(*psz0) , Len(*psz1))
? Search(1 , psz0 , psz1 , Len(*psz0) , Len(*psz1))
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
DarkDemon | Дата: Среда, 16.10.2024, 08:56 | Сообщение # 2 |
Полковник
Группа: Друзья
Сообщений: 199
Статус: Offline
| Стас, расскажи насколько он быстрый? И тот что в теме рядом(поиск по z которая). Ты же стопудово сравнивал.
|
|
| |
haav | Дата: Среда, 16.10.2024, 17:10 | Сообщение # 3 |
Генералиссимус
Группа: Администраторы
Сообщений: 1372
Статус: Offline
| Цитата DarkDemon ( ) Стас, расскажи насколько он быстрый? И тот что в теме рядом(поиск по z которая). Ты же стопудово сравнивал.
Данный алгоритм (Бойера-Мура-Хорспула) довольно быстрый и работает примерно с той же скоростью , что и Instr. Сама же функция Instr построена по алгоритму KMP. В этой ветке я добавил адаптированный вариант функции Instr на языке FB:
https://freebasic.ucoz.com/forum/5-610-1
Алгоритмы же написанные нейросетью где-то не очень оптимизированы. Но согласись , что и так довольно неплохо для автомата.
Вообще если сравнивать Бойера-Мура-Хорспула и Кнута-Морриса-Пратта (KMP) , то все зависит от того , где находится искомая строка. В каких-то ситуациях выигрывает Бойера-Мура-Хорспула , а в каких-то KMP
Что касается Z-алгоритма , то не разбирался , но при общем применении (в моем тестировании) он проигрывает обоим алгоритмам (Бойера-Мура-Хорспула (BMH) и Кнута-Морриса-Пратта (KMP))
Вообще вот какие области применения дает сама нейросетка:
Прямой (линейный) метод поиска: Применять в простых случаях, когда подстрока короткая или строка небольшая. Использовать для демонстрационных целей или обучения алгоритмам поиска. Включать в системы поиска, которые не требуют быстрой обработки. Метод Кнута-Морриса-Пратт (КМП): Применять для поиска одной подстроки в строке с повторным использованием. Использовать в системах поиска текста, где требуется быстрая и эффективная обработка. Включать в системы поиска, которые требуют минимизации операций. Метод Бойера-Мура: Применять для поиска одной подстроки в строке с повторным использованием и большой длиной строки. Использовать в системах поиска текста, где требуется высокая скорость и эффективность. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости. Метод Рабина-Карпа (РК): Применять для поиска множества подстрок в строке с повторным использованием. Использовать в системах поиска текста, где требуется быстрая и эффективная обработка множества запросов. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости. Метод Уэлча: Применять для поиска множества подстрок в строке с повторным использованием и большой длиной строки. Использовать в системах поиска текста, где требуется высокая скорость и эффективность. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости. Алгоритмы суффиксного дерева: Применять для поиска всех вхождений подстроки в строке с повторным использованием. Использовать в системах поиска текста, где требуется быстрая и эффективная обработка всех вхождений. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости. Алгоритмы суффиксного массива: Применять для поиска всех вхождений подстроки в строке с повторным использованием. Использовать в системах поиска текста, где требуется быстрая и эффективная обработка всех вхождений. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости. Алгоритм Z-функции: Применять для поиска всех вхождений подстроки в строке с повторным использованием. Использовать в системах поиска текста, где требуется быстрая и эффективная обработка всех вхождений. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости. Алгоритм Aho-Corasick: Применять для поиска множества подстрок в строке с повторным использованием. Использовать в системах поиска текста, где требуется быстрая и эффективная обработка множества запросов. Включать в системы поиска, которые требуют минимизации операций и максимизации скорости.
P.S. Все исходные коды написаны для общего случая. Если же надо искать скажем одну и ту же строку в разных текстах для алгоритма Бойера-Мура-Хорспула , то поиск можно значительно ускорить , если "генерацию таблицы" делать единожды , а потом только выполнять поиск. В случае KMP алгоритма все тоже самое. И алгоритмы станут работать значительно эффективнее.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
haav | Дата: Среда, 16.10.2024, 17:14 | Сообщение # 4 |
Генералиссимус
Группа: Администраторы
Сообщений: 1372
Статус: Offline
| Код алгоритма "Z-алгоритм" был искарежен движком форума. Сейчас вроде исправил и он должен собираться.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
DarkDemon | Дата: Среда, 16.10.2024, 19:06 | Сообщение # 5 |
Полковник
Группа: Друзья
Сообщений: 199
Статус: Offline
| Позже потестирую, надо изучить эти алгоритмы, хотя бы самые эффективные, сейчас с ходу трудно вникать. У меня был на уме стохастический алг, для длины строки до 1000 символов, завести массивы, где хранить уникальный рассчитанный случайным образом(RND) номер символа, и по этому шаблону искать, если хоть одно несовпадение, сразу выходить. Думаю будет работать охуенно быстро. Пол мегабайта на кеширование индексов мне не жалко. Можно и на более длинные завести, но для текста оно не требуется, а те, что выходят за пределы - считать обычным способом. Но ещё не проверял свой алг, надо скодить, посмотреть.
|
|
| |
haav | Дата: Среда, 16.10.2024, 20:43 | Сообщение # 6 |
Генералиссимус
Группа: Администраторы
Сообщений: 1372
Статус: Offline
| Цитата У меня был на уме стохастический алг,
Даже не знаю , о чем ты. Но если получится что-то стоящее , хотелось бы глянуть.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |
|