Spelling suggestions: "subject:"rabiner"" "subject:"rabinal""
1 |
Using Rabin-Karp fingerprints and LevelDB for faster searchesDeighton, Richard A. 01 December 2012 (has links)
This thesis represents the results of a study into using fingerprints generated according to the Rabin-Karp Algorithm, and a database LevelDB to achieve Text Search times below GREP, which is a standard command-line UNIX text search tool.
Text Search is a set of algorithms that find a string of characters called a Search Pattern in a much larger string of characters in a document we call a text file.
The Rabin-Karp Algorithm iterates through a text file converting character strings into fingerprints at each location. A fingerprint numerically represents a window length string of characters to the left of its location. The algorithm compares the calculated fingerprint to the Search Pattern’s fingerprint. When fingerprints are not equal, we can guarantee the corresponding strings will not match. Whereas when fingerprints are, the strings probably match. A verification process confirms matches by checking respective characters.
Our application emerges after making the following major changes to the Rabin-Karp Algorithm. First, we employ a two-step technique rather than one. During step 1, the preprocessing step, we calculate and store fingerprints in a LevelDB database called an Index Database. This is our first major change unique to us. Step 2, the matching step, is our second unique change. We use the Index Database to look-up the Search Pattern’s fingerprint and gather its set of locations. Finally, we allow the pattern to be any length relative to the window length. We even created an equation to check if the difference in length is too long for the fingerprint’s number system base.
We facilitated our performance experiments by first building our application and testing it against GREP for a wide range of different parameters. Our conclusions and recommendations determine that although we currently only outperform GREP in about half the cases, we identify some promising opportunities to modify some parts of our application so that we can outperform GREP in all instances. / UOIT
|
2 |
Autolab : Ett automatiskt laborationsrättningssystem / Autolab : An automated laboratory work correction systemNorström, Mikael January 2017 (has links)
Användningen av automatiserade system är en vanlig lösning för att underlätta en manuell arbetsbörda inom många områden. Autolab är en prototyp av ett automatiskt laborationsrättningssystem avsett att kunna användas som ett hjälpmedel inom undervisning för att reducera arbetsbördan för lärare. Examensarbetet har inneburit att skapa och integrera ny funktionalitet till systemet. Bland annat att skapa en enklare plagiatkontroll baserad på strängmatchning för att upptäcka och förhoppningsvis förbygga fusk mellan studenters inlämnade laborationer. För att underlätta förståelsen till användare för hur Autolab fungerar skapades dokumentation över hur systemet används som både lärare och student. Efter att analyserat vad som implementerats till Autolab ges förslag på vad som kan förbättras i systemet till framtiden.
|
Page generated in 0.0312 seconds