# Python 2 and 3 compatibility
# pip install future
from __future__ import (absolute_import, division,
print_function, unicode_literals)
from builtins import *
Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах и т.д.
Дан текст t и образец p (считаем, что |p| < |t|).
Задача: найти все вхождения образца p в текст t
Алгоритм:
Сложность в худшем случае: O ( |t| * |p| )
def naive_match(p, t):
assert len(p) <= len(t) # assume text at least as long as pattern
occurrences = []
for i in range(0, len(t)-len(p)+1): # for each alignment of p to t
match = True # assume we match until proven wrong
for j in range(0, len(p)): # for each position of p
if t[i+j] != p[j]:
match = False # at least 1 char mismatches
break
if match:
occurrences.append(i)
return occurrences
t = 'I need a needle in a haystack' # "text" - thing we search in
p = 'needle' # "pattern" - thing we search for
naive_match(p, t)
[9]
Убедимся, что needle
действительно найдено
t[9: 9 + len(p)]
'needle'
naive_match('needle', 'needleneedleneedle')
[0, 6, 12]
Такая сложность алгоритма - непозволительная роскошь для поиска в больших текстах.
Посмотрим, как замена строки на некоторый вектор может помочь в таких задачах как поиск подстроки и сжатие строки.
Пусть дана строка s длины n. Тогда Z-функция ("зет-функция") от этой строки — это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.
Пример: Z(abcdabscabcdabia)=[16,0,0,0,2,0,0,0,6,0,0,0,2,0,0,1]. Еще примеры и описание алгоритма на сайте e-maxx.
Ниже приведен код (опционально).
def z_func(s):
Z = [len(s)] + [0] * len(s)
assert len(s) > 1
# Initial comparison of s[1:] with prefix
for i in range(1, len(s)):
if s[i] == s[i-1]:
Z[1] += 1
else:
break
r, l = 0, 0
if Z[1] > 0:
r, l = Z[1], 1
for k in range(2, len(s)):
assert Z[k] == 0
if k > r:
# Case 1
for i in range(k, len(s)):
if s[i] == s[i-k]:
Z[k] += 1
else:
break
r, l = k + Z[k] - 1, k
else:
# Case 2
# Calculate length of beta
nbeta = r - k + 1
Zkp = Z[k - l]
if nbeta > Zkp:
# Case 2a: Zkp wins
Z[k] = Zkp
else:
# Case 2b: Compare characters just past r
nmatch = 0
for i in range(r+1, len(s)):
if s[i] == s[i - k]:
nmatch += 1
else:
break
l, r = k, r + nmatch
Z[k] = r - k + 1
return Z
z_func('abracadabra')
# abracadabra (11)
# a (1)
# a (1)
# abra (4)
# a (1)
[11, 0, 0, 1, 0, 1, 0, 4, 0, 0, 1, 0]
z_func('aaaaa')
[5, 4, 3, 2, 1, 0]
Применения Z-функции:
Пусть t - текст, p - образец.
Задача: найти все вхождения образца p в текст t.
Решение:
Сложность: O(len(p) + len(t))
Код
def zMatch(p, t):
s = p + "$" + t
Z = z_func(s)
occurrences = []
for i in range(len(p) + 1, len(s)):
if Z[i] == len(p):
occurrences.append(i - (len(p) + 1))
return occurrences
Иллюстрация: Текст "lambalambalam", ищем в нем "lamb"
t, p = "lambalambalam", "lamb"
calculated_z = z_func("lamb$lambalambalam")
print(calculated_z)
[18, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4, 0, 0, 0, 0, 3, 0, 0, 0]
Для первого индекса есть вхождение:
print(len(p), calculated_z[0 + len(p) + 1])
4 4
Для второго - нет:
print(len(p), calculated_z[1 + len(p) + 1])
4 0
zMatch("lamb", "lambalambalam")
[0, 5]
Еще примеры
t, p = 'haystack needle haystack', 'needle'
print(z_func(p + '$' + t))
zMatch('needle', 'haystack needle haystack')
[31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[9]
t, p = 'haystack needle needle', 'needle'
print(z_func(p + '$' + t))
zMatch('needle', 'haystack needle needle')
[29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0]
[9, 16]
Дана строка s длины n.
Задача: найти самое короткое её "сжатое" представление, т.е. найти такую строку t наименьшей длины, что s можно представить в виде конкатенации одной или нескольких копий t.
def compress_with_z(s):
z_vec = z_func(s)
for i in range(1, len(s)):
if (i + z_vec[i] == len(s)) and (z_vec[i] % i == 0):
return s[:i]
else:
return s
s = "footfootfootfootfoot"
print(z_func(s))
print(compress_with_z(s))
[20, 0, 0, 0, 16, 0, 0, 0, 12, 0, 0, 0, 8, 0, 0, 0, 4, 0, 0, 0, 0] foot