FreeBasic
Главная
Вход
Регистрация
Четверг, 05.12.2024, 19:27Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Алгоритм поиска Бойера-Мура-Хорспула
haavДата: Понедельник, 14.10.2024, 08:47 | Сообщение # 1
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Репутация: 50
Статус: 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
Полковник
Группа: Друзья
Сообщений: 200
Репутация: -1
Статус: Offline
Стас, расскажи насколько он быстрый? И тот что в теме рядом(поиск по z которая).
Ты же стопудово сравнивал.
 
haavДата: Среда, 16.10.2024, 17:10 | Сообщение # 3
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Репутация: 50
Статус: 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
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Репутация: 50
Статус: Offline
Код алгоритма "Z-алгоритм" был искарежен движком форума. Сейчас вроде исправил и он должен собираться.

Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
DarkDemonДата: Среда, 16.10.2024, 19:06 | Сообщение # 5
Полковник
Группа: Друзья
Сообщений: 200
Репутация: -1
Статус: Offline
Позже потестирую, надо изучить эти алгоритмы, хотя бы самые эффективные, сейчас с ходу трудно вникать.
У меня был на уме стохастический алг, для длины строки до 1000 символов, завести массивы, где хранить уникальный
рассчитанный случайным образом(RND) номер символа, и по этому шаблону искать, если хоть одно несовпадение,
сразу выходить. Думаю будет работать охуенно быстро. Пол мегабайта на кеширование индексов мне не жалко.
Можно и на более длинные завести, но для текста оно не требуется, а те, что выходят за пределы - считать обычным
способом. Но ещё не проверял свой алг, надо скодить, посмотреть.
 
haavДата: Среда, 16.10.2024, 20:43 | Сообщение # 6
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Репутация: 50
Статус: Offline
Цитата
У меня был на уме стохастический алг,


Даже не знаю , о чем ты. Но если получится что-то стоящее , хотелось бы глянуть.


Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
  • Страница 1 из 1
  • 1
Поиск: