diff options
| -rw-r--r-- | ass1/binary_boyermoore.py | 5 | ||||
| -rw-r--r-- | ass1/editdist.py | 28 |
2 files changed, 12 insertions, 21 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py index df75d62..3b3c29f 100644 --- a/ass1/binary_boyermoore.py +++ b/ass1/binary_boyermoore.py @@ -1,9 +1,8 @@ -import sys +# Alexander Occhipinti - 29994705 - FIT3155 S1/2021 +import sys def alpha_number(char): - if char == "0" or char == "1": - return int(char) return ord(char) - 97 diff --git a/ass1/editdist.py b/ass1/editdist.py index 44e9efd..db359fe 100644 --- a/ass1/editdist.py +++ b/ass1/editdist.py @@ -1,5 +1,8 @@ +# Alexander Occhipinti - 29994705 - FIT3155 S1/2021 + import sys + def compare(string, i, end): for j in range(end): if i+j == end or string[i+j] != string[j]: @@ -38,34 +41,22 @@ def reverse(string): return string[::-1] -def comapre_zs(z_prefix, z_suffix, pat_length): - with open(OUTPUT_PATH, "w") as file: - for i in range(pat_length+1, len(z_prefix)-pat_length-1): - distance = None - if z_prefix[i] == pat_length: - distance = 0 - elif z_prefix[i] + z_suffix[i] >= pat_length-1: - distance = 1 - if distance is not None: - file.write(f"{i-pat_length-1} {distance}\n") - print(f"===={i-pat_length-1} {distance}") - print(i-pat_length-1, z_prefix[i], z_suffix[i]) - def match(z_prefix, z_suffix, pat_length): matches = [] l = pat_length+1 r = len(z_prefix)-1 - while l < len(z_prefix): # while l hasn't reached the end + while l < len(z_prefix): # while l hasn't reached the end if z_prefix[l] != 0 and z_suffix[r] != 0: distance = None if z_prefix[l] == pat_length: - distance = 0 + distance = 0 # The left and right pointer align at an exact pattern match elif z_prefix[l] + z_suffix[r] >= pat_length - 1: - distance = 1 + distance = 1 # The left and right pointer align at a match of distance one if distance is not None: matches.append((l-pat_length-1, distance)) l += 1 r += 1 + # Progress each pointer until matches are found if z_prefix[l] == 0: l += 1 if z_suffix[r] == 0: @@ -74,8 +65,10 @@ def match(z_prefix, z_suffix, pat_length): def edit_distance(txt, pat): + # Do Z algorithm twice, forwards (prefix) and backwards (suffix) forwards = pat + "$" + txt backwards = reverse(pat) + "$" + reverse(txt) + # Match the Z_prefix values with the Z_suffix backwards tuples = match(gusfield(forwards), gusfield(backwards), len(pat)) print(f"Found {len(tuples)} matches of edit distance <= 1.") output(tuples) @@ -104,6 +97,5 @@ def main(): txt, pat = read_args() edit_distance(txt, pat) -if __name__ == '__main__': - main() +main() |