|
Алгоритм поиска КМП (Кнута-Морриса-Пратта)
|
|
| haav | Дата: Понедельник, 14.10.2024, 08:30 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 1400
Статус: Offline
| Это алгоритм поиска Кнута-Морриса-Пратта , код которого был написан AI. Заслуга AI довольно большая для этого кода , но все таки мне пришлось ему помогать и немножко исправлять. Но все равно неплохо получилось.
Код ' Функция KmpSearch ищет подстроку subStr в строке mainStr, начиная с позиции iStartPosition.
Function KmpSearch(mainStr As String, subStr As String, iStartPosition As Integer = 1) As Long
Dim i As Integer, j As Integer, cl As Integer
' Проверяем, что mainStr не пустая строка. Если да, возвращаем 0.
If Len(mainStr) = 0 Then
Return 0
Endif
' Получаем длину подстроки subStr.
Dim iLen As Integer = Len(subStr)
' Если subStr пустая, возвращаем 0.
If iLen = 0 Then
Return 0
' Если subStr состоит из одного символа, ищем его в mainStr и возвращаем позицию.
Elseif iLen = 1 Then
For i As Integer = iStartPosition - 1 To Len(mainStr) - 1
If mainStr[i] = subStr[0] Then
Return i + 1
Endif
Next
Return 0
Endif
' Создаем массив lps для хранения длины наибольшего суффикса, который является префиксом.
Dim lps(iLen) As Integer
' Инициализируем переменные.
cl = 0
i = 1
' Заполняем массив lps для подстроки subStr.
While i < iLen
If subStr[i] = subStr[cl] Then
cl += 1
i += 1
Elseif cl <> 0 Then
cl = lps(cl - 1)
Else
i += 1
Endif
Wend
' Заполняем массив lps.
For j As Integer = 0 To iLen - 2
If subStr[j + 1] = subStr[cl] Then
cl += 1
Endif
lps(j) = cl
Next j
' Инициализируем переменные для поиска.
i = iStartPosition - 1
j = 0
' Основной цикл поиска подстроки в строке.
While i < Len(mainStr)
If mainStr[i] = subStr[j] Then
i += 1
j += 1
If j = iLen Then
Return i - iLen + 1
Endif
Elseif j <> 0 Then
j = lps(j - 1)
Else
i += 1
Endif
Wend
' Если подстрока не найдена, возвращаем 0.
Return 0
End Function
' Пример использования функции KmpSearch.
Dim mainStr As String = "DABCD"
Dim subStr As String = "BCD"
Print KmpSearch(mainStr, subStr , 2)
А это описание AI для данного кода:
Цитата Алгоритм работы функции KmpSearch можно описать следующим образом:
Инициализация: Функция принимает три параметра: mainStr (основная строка), subStr (подстрока) и iStartPosition (начальная позиция для поиска). Если mainStr пуста, функция возвращает 0.
Проверка длины подстроки: Если subStr пустая, функция также возвращает 0. Если subStr состоит из одного символа, функция ищет этот символ в mainStr, начиная с позиции iStartPosition - 1, и возвращает позицию найденного символа или 0, если символ не найден.
Построение массива lps: Создаётся массив lps длиной, равной длине subStr. Этот массив поможет в алгоритме Кнута-Морриса-Пратта (KMP). Функция заполняет этот массив значениями, которые показывают длину наибольшего суффикса, являющегося одновременно и префиксом.
Заполнение массива lps: Для каждого символа в subStr кроме последнего, функция проверяет, совпадает ли текущий символ с символом на позиции cl (количество совпадений). Если символы совпадают, увеличиваем cl. В противном случае, если cl не равно 0, переходим к предыдущему значению lps, хранящемуся в массиве.
Поиск подстроки: Функция снова проходит по mainStr, начиная с позиции iStartPosition - 1. Она использует переменные i и j для отслеживания текущих позиций в mainStr и subStr соответственно. Если символы на этих позициях совпадают, обе позиции увеличиваются. Если j достигает длины subStr, функция возвращает позицию найденного символа в mainStr.
Возврат результата: Если подстрока не найдена, функция возвращает 0.
В целом, данный код реализует алгоритм Кнута-Морриса-Пратта для поиска подстроки в строке. Он использует предварительное построение префикс-функции (массив lps), чтобы оптимизировать процесс поиска, избегая повторных сравнений символов.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Среда, 16.10.2024, 16:41 | Сообщение # 2 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1400
Статус: Offline
| А это адаптированный на FB код функции Instr:
Код #include "crt.bi"
'This code is essentially an adaptation of the INSTR code in the FREEBASIC language!!!
Function search _
(_
start As Integer, _
pachText As Zstring Ptr, _
len_text As Integer, _
pachPattern As Zstring Ptr, _
len_pattern As Integer _
) As Integer
Dim As Integer i, j, len_max = len_text - len_pattern
Dim As Integer bm_bc(256)
Dim As Integer Ptr bm_gc, suffixes
Dim As Integer ret
bm_gc = malloc(Sizeof(Integer) * (len_pattern + 1))
suffixes = malloc(Sizeof(Integer) * (len_pattern + 1))
memset( bm_gc, 0, Sizeof(Integer) * (len_pattern+1) )
memset( suffixes, 0, Sizeof(Integer) * (len_pattern+1) )
'/* create "bad character" shifts */
memset(@bm_bc(0), -1 , Ubound(bm_bc)*Sizeof(Integer))
While i <> len_pattern
bm_bc( pachPattern[i] ) = i
i+=1
Wend
'/* preprocessing for "good end strategy" case 1 */
i = len_pattern
j=len_pattern+1
suffixes[ i ] = j
While ( i<>0 )
Dim As Ubyte ch1 = (*pachPattern)[i-1]
While ( j<=len_pattern Andalso ch1<>(*pachPattern)[j-1] )
If( bm_gc[j]=0 ) Then
bm_gc[j] = j - i
Endif
j = suffixes[j]
Wend
i-=1
j-=1
suffixes[i] = j
Wend
'/* preprocessing for "good end strategy" case 2 */
j = suffixes[0]
For i=0 To len_pattern
If( bm_gc[i]=0 ) Then
bm_gc[i] = j
Endif
If( i=j ) Then
j = suffixes[j]
Endif
Next
ret = 0
'/* search */
i=start
While( i <= len_max )
j = len_pattern
While( j<>0 Andalso (*pachPattern)[j-1]=(*pachText)[i+j-1] )
j-=1
Wend
If( j=0 ) Then
ret = i + 1
Exit While
Else
Dim As Ubyte chText = (*pachText)[i+j-1]
Dim As Integer shift_gc = bm_gc[j]
Dim As Integer shift_bc = j - 1 - bm_bc( chText)
If shift_gc > shift_bc Then
i+=shift_gc
Else
i+=shift_bc
Endif
Endif
Wend
free( bm_gc )
free( suffixes )
Return ret
End Function
'##############################TESTs############################
Dim As Zstring Ptr pszBuf = Allocate(100001)
For i As Long = 0 To 99990
pszBuf[i] = Rnd*100+30
Next
pszBuf[99991] = 77
pszBuf[99992] = 77
pszBuf[99993] = 77
pszBuf[99994] = 77
pszBuf[99995] = 77
pszBuf[99996] = 78
pszBuf[99997] = 79
pszBuf[99998] = 80
pszBuf[99999] = 81
pszBuf[100000] = 0
Dim As Zstring Ptr pszTemplate = @"MMMMMNOPQ"
? "INSTR , WRITEN in FB"
Var t = Timer
For i As Long = 0 To 100
Dim As Integer iLenBuf = Len(*pszBuf)
Dim As Integer iLenTemplate = Len(*pszTemplate)
Search(0 , pszBuf , iLenBuf , pszTemplate , iLenTemplate)
Next
? Timer -t
? "INSTR , WRITEN in C"
t = Timer
For i As Long = 0 To 100
Instr(*pszBuf , *pszTemplate)
Next
? Timer -t
Чтобы достичь той же скорости , что и у Instr , код надо компилировать с опцией оптимизации -O 3
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| DarkDemon | Дата: Понедельник, 17.03.2025, 08:49 | Сообщение # 3 |
|
Полковник
Группа: Друзья
Сообщений: 218
Статус: Offline
| Нашёл визуально более менее понятное толкование КМП: https://www.youtube.com/watch?v=7g-WEBj3igk
Тут поясняют что такое суффикс и префикс. Правда не поясняют напрямую что такое "массив пи" или lps в коде выше.
Хотя кого я обманываю, нихрена не понятно))) надо кодить и гонять. Типа преданализ совпадений,
но почему в подстроке, а вот хрен его знает, типа она не может быть больше строки, но может быть и не сильно меньше.
Короче чисто логико-математически надо ковырять. На первый взгляд гибридизация и улучшение этого алгоритма
недопустима, т.к. он полностью самодостаточен.
С другой стороны, очень уж дофига проверок, т.к. суффиксы и префиксы мы сравниваем как говориться "directly".
На этом идёт потеря. Выигрыш идёт если подстрока небольшая, а строка длинная. Т.е. стабильность сильно зависит
от статистических данных. И все чудеса, если они есть, творит именно оптимизатор.
Сообщение отредактировал DarkDemon - Понедельник, 17.03.2025, 08:50 |
| |
| |
|
