aboutsummaryrefslogtreecommitdiff
path: root/ass1/binary_boyermoore.py
diff options
context:
space:
mode:
Diffstat (limited to 'ass1/binary_boyermoore.py')
-rw-r--r--ass1/binary_boyermoore.py79
1 files changed, 25 insertions, 54 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py
index 380eacf..4c41c77 100644
--- a/ass1/binary_boyermoore.py
+++ b/ass1/binary_boyermoore.py
@@ -11,7 +11,6 @@ def alpha_number(char):
if char == "0" or char == "1":
return int(char)
return ord(char) - 97
- # return int(char)
def reverse(string):
@@ -106,96 +105,72 @@ def boyer_moore(pat, txt):
R, good_suffix, matched_prefix = preprocess(pat)
m = len(pat)
n = len(txt)
+ i = m-1
j = 0
- occurrence = 0
+ occurrences = []
galils = 0
comps = 0
-
- # print("="*15)
- # print(6*" " + txt)
- i = m-1
galil = False
- start = None
- stop = None
+ start = 0
+ stop = 0
while j <= n-m:
- # print(f"{j=:02} {' ' * j}", end="")
- # for x in range(len(pat)):
- # if x == i:
- # print(pat[x].upper(), end="")
- # else:
- # print(pat[x], end="")
- # print()
match = pat[i] == txt[j+i]
comps += 1
if match:
if galil and stop >= i > start:
galils += 1
- assert start >= 0
i = max(start-1, 0)
galil = False
if i == 0:
good_suffix_shift = m - matched_prefix[1]
j += good_suffix_shift
- occurrence += 1
+ occurrences.append(j)
i = m-1
else:
i -= 1
else:
- galil = False
- mp = False
- gs = False
mismatched = txt[j + i]
bad_char_shift = i - R[alpha_number(mismatched)][i]
good_suffix_shift = 1
if good_suffix[i+1] > 0:
good_suffix_shift = m - good_suffix[i+1]
- gs = True
start = good_suffix[i+1] - m + i + 1
stop = good_suffix[i+1]
elif good_suffix[i+1] == 0:
good_suffix_shift = m - matched_prefix[i+1]
- mp = True
start = 0
stop = matched_prefix[i + 1]
best_shift = max(good_suffix_shift, bad_char_shift)
j += best_shift
- galil = (mp or gs) and best_shift == good_suffix_shift
+ galil = best_shift == good_suffix_shift
i = m-1
-
- print(f"It found {occurrence} occurences.")
- print(f"Galil'd {galils} times.")
- # print(f"\n {list(range(m))}")
- # print("" + str(list(map(int, pat))))
- # for i, a in enumerate(R):
- # print(chr(i+97), a)
- # print(good_suffix)
- # print(matched_prefix)
- print(f"{comps} comparisons.")
- return comps, occurrence
+ print(comps)
+ return comps, occurrences
def two_to_the(n):
return 1 << n
def chunky_search(pat, txt, factor=2):
- occurrence = 0
+ occurrences = []
comps = 0
for offset in range(two_to_the(factor-1)):
padding = format(offset, f"0{factor-1}b") if len(pat) % factor else ""
augmented_pat = f"{pat}{padding}"
- # print(padding)
- print(condense(format(two_to_the(factor)-1, f"0b"), 0, factor))
c, o = boyer_moore(condense(augmented_pat, 0, factor), condense(txt, offset, factor))
comps += c
- occurrence += o
+ print(offset, o)
+ occurrences += o
base_comps, base_occur = boyer_moore(pat, txt)
+ print(base_occur[:20])
+ print(occurrences[:10])
print("*"*20)
- print(f"Chunky Optimisation: {occurrence} occurences in {comps} comparisons.")
- print(f"Normal: {base_occur} occurences in {base_comps} comparisons.")
- # assert base_occur == occurrence
+ print(f"Chunky Optimisation: {len(occurrences)} occurences in {comps} comparisons.")
+ print(f"Normal: {len(base_occur)} occurences in {base_comps} comparisons.")
if base_comps > 0:
print(f"{comps * 100 / base_comps:.3f}% of normal Boyer-Moore")
print(f"{comps * 100 / 642096:.3f}% of their Boyer-Moore")
+ return comps, occurrences
def read_args():
with open(sys.argv[1], "r") as txt_file:
@@ -204,23 +179,19 @@ def read_args():
pat = pat_file.read()
return txt, pat
-# boyer_moore(condense("01100010"), condense(a))
-# boyer_moore(condense("01100011"), condense(a, offset=1))
+def output_matches(occurrences):
+ with open("output_binary_boyermoore.txt", "w") as file:
+ for o in occurrences:
+ file.write(f"{o}\n")
def main():
- F = 2
+ factor = 2
if len(sys.argv) < 3:
print("Not enough arguments!")
else:
txt, pat = read_args()
- chunky_search(pat, txt, factor=F)
-
-main()
-
-
-
+ comps, occurrences = chunky_search(pat, txt, factor)
+ print(comps)
+ output_matches(occurrences)
-# boyer_moore("111000110", "01110111010101110100101011101101111011111111111111100011001110111010101110100101011101101101110111010110111010010101110110110111011111011011")
-# print(condense("1110000110"))
-# print(condense("1110000110", offset=1))
-# boyer_moore("111011011001110", "101010111010010101110111010101110100101011101101111011111111111101110111010101110100101011101101101110111010101110100101011101101101110111110110110011100000110101011101001010111011011011101100001010101110100101011101110101011101001010111011011011101110101011101001010111011011011101110101011101001010111011011011101100001101010111010010101110110110111011000010111011111011101110110101110110101101100000001011001010101010101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010100001011101111101110111011010111011010110110000000101100101010101010101011101001010111011011011101100001011101111101110111011010101110100101011101101101110110000101110111110101010111010010101110110110111011000010111011101010111010010101110110110111011000010111010101110100101011101101101010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101111011000010111011111011101110110101110110101101100000001011001010101010110111110111011101101011101101011011000000010110010101010101111011101110110101110110101101100000001011001010101010111101110110101110110101101100000001011001010101010110101110110101101100000001011001010101010110110111011000010101011101001010111011101010111010010101110110110111011101010111010010101110110110111011101010111010010101110110110111011000011010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111101111111111111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101") \ No newline at end of file
+main() \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2025-10-26 20:25:38 +0000