Knyffen
b9645f15ff
The text and pattern are now streamed directly (skipping saving them to strings). Knowing exactly what string was matched has now been delegated to the Rabin_fingerprint_process. |
||
|---|---|---|
| books | ||
| helper_code | ||
| to_be_rewritten_bin | ||
| V1 | ||
| .gitignore | ||
| compare_fingerprint_false_positive_probabilities.sage | ||
| general_library.cpp | ||
| general_library.hpp | ||
| Makefile | ||
| processes.cpp | ||
| processes.hpp | ||
| Rabin_fingerprint.cpp | ||
| Rabin_fingerprint.hpp | ||
| README.md | ||
| simple_string_matching | ||
| simple_string_matching.cpp | ||
| test_rabin_fingerprint.sage | ||
Bachelor's_Thesis_Code
Code used for my Bachelor's Thesis
Issues
When reading the pattern from a file, according to UNIX standards (read details here) a "text file" has to end on a newline.
This adds an unintended newline to the end of the pattern, so to avoid adding said newline, write the file using:
echo -n word > pattern.txt
or if you use Vim, remove the newline using
:set binary
:set noeol
:wq
Versions
Current Version
Compared to V1, in this current state generate_initial_irreducible_polynomials.sage, generate_random_irreducible_polynomial.sage, and multiply_polynomials_modulo_polynomial.sage have been removed from the main folder, as they have already been used for implementing their corresponding features in general_library.cpp. They will be preserved in the V1 folder.
This version also contains code relating to Porat-Porat and other random code stumps. This code is going to be completely reimplemented, but is preserved for now to avoid redoing work.
V1
general_library.cpp
- Exports functions for:
- Generating a random irreducible polynomial of degree up to 31.
- Contains code for:
- Contains code to multiply polynomials modulo another polynomial.
- Doesn't contain code to initially calculate modulo a polynomial. It requires the initial polynomials to all be at most of the same degree as the polynomial that you use for modulo.
- A very custom version of calculating Reduced Row Echelon Form assuming all values are in Z2.
generate_initial_irreducible_polynomials.sage
- Generates a list of irreducible polynomials, one of each degree. The polynomials are printed in a format that can be copy-pasted directly into
general_library.cpp.
generate_random_irreducible_polynomial.sage
- Contains an general template of how
general_library.cppshould implement generating a random irreducible polynomial. The output of this program can also be used for debugging, since it uses many (correctly implemented) built-in sagemath functions that have to manually implemented ingeneral_library.cpp.
multiply_polynomials_modulo_polynomial.sage
- Contains a general template of how
general_library.cppshould implement multiplying polynomials modulo a polynomial in Z2.
compare_fingerprint_false_positive_probabilities.sage
- Contains initial (i.e. very rouch) code, which compares the upper bounds of a false match occuring of the Rabin fingerprint and the fingerprint used in Karp-Rabin.
test_rabin_fingerprint.sage
- Contains initial (i.e. very rough) code which debunks my theory that modulo a prime is somewhat equivalent to modulo an irreducible polynomial.