Compare contrast Rabin Karp Algorithm vs Knuth-Morris-Pratt Algorithm

Text Plagiarism

To check for plagiarism in a text file using the Rabin-Karp algorithm, you would compare the text file against a set of known documents or phrases (potential sources of plagiarism) to identify matching sequences.

Performance Metric 1 : Execution Time

• Observations : In this case we can see KMP uses much less time than the Robin-Carp algorithm.
• System metrics : I used one single thread for both and for Robin carp I used prime number as 101 means it may have some hash collisions.
• Improvements : We can use Multi thread for Robin Carp , We can use better prime number to reduce hash collisions Overall : Rabin-Karp is favored in many real-world plagiarism detection systems because of its flexibility in handling multiple patterns and its efficiency in large-scale comparisons.

Performance Metric 2 : Memory Consumption

• Observations : In this case we can see Robin-Carp uses much less time than the KMP algorithm.
• System metrics : This contains size of input file (50kb), copies of data to concat as string, arrays and lists, python memory management etc
• Improvements : consider optimizing the function by reducing the size of intermediate data structures, avoiding unnecessary copies, or using more memory-efficient algorithms or data structures.
• Overall : Rabin-Karp is favored in many real-world plagiarism detection systems because of its flexibility in handling multiple patterns and its efficiency in large-scale comparisons.

Performance Metric 3 : Algorithm Hyper-Parameter

Number of Hash Collisions for Different Prime Numbers and Execution Time for Different Prime Numbers

• Observation : In here we can see for 101 prime number it gives less hash collisions and less execution time. Because when the prime number increases it requires more computation power for modular operations. The other thing is large primes means less efficient use of CPU caches

Algorithmic Metric 1 : Algorithm Efficiency

Rabin-Karp Algorithm: Rabin-Karp is particularly effective for detecting plagiarism when multiple patterns need to be matched simultaneously. It can handle multiple patterns with just a single pass through the text, thanks to its hash-based approach and capability of working on multi threads.

KMP Algorithm: KMP is highly efficient for single-pattern matching and is well-suited for scenarios where the pattern and text are large. Its predictable linear time complexity makes it reliable for plagiarism detection, especially when dealing with long documents or DNA sequences.

Algorithmic Metric 2 : Time Complexity

Rabin-Karp has an average-case time complexity of O(n+m) and KMP has O(n), where n is the length of the text and m is the length of the pattern. However, real-world performance is influenced by many practical factors, like the overhead of hash calculations in Rabin-Karp or the memory access patterns in KMP.

Algorithmic Metric 3 : Ease of Implementation

Rabin-Karp: Easier to implement, especially for multiple patterns, but involves understanding hashing. KMP: Slightly more complex due to the preprocessing step (LPS array), but very efficient and consistent for single-pattern matching.

Conclusion for Text Plagiarism :

• Multiple Pattern Matching: Rabin-Karp excels at checking multiple patterns simultaneously, which is often necessary in text plagiarism detection where you might be looking for several phrases or passages at once.
• Hashing Flexibility: The algorithm uses a rolling hash, allowing quick comparisons of different parts of the text. This makes it effective in scenarios where you need to scan large bodies of text for potential matches.
• Efficiency with Large Texts: Although it can experience hash collisions, with a well-chosen hash function and prime number, Rabin-Karp can handle large texts efficiently, making it ideal for scanning entire documents for copied content.

DNA Plagiarism

To check for plagiarism in a DNA sequence we need to do searches for specific DNA subsequences (patterns) within a larger DNA sequence (text).

Performance Metric 1 : Execution Time

• Observations : In this case we can see KMP uses much less time than the Robin-Carp algorithm.
• System metrics : I used one single thread for both and for Robin carp I used prime number as 101 means it may have some hash collisions.
• Improvements : If the patterns you are searching for are short and appear infrequently, the difference in execution time between KMP and Rabin-Karp may be minimal, as both algorithms can quickly match or discard the patterns.
• Overall : KMP is efficient because it avoids redundant comparisons by using the LPS (Longest Prefix Suffix) array. This makes it particularly suitable for longer patterns or texts where partial matches frequently occur.

Performance Metric 2 : Memory Consumption

• Observations : In this case we can see KMP uses much less memory consumption than the Robin-Carp algorithm.
• Overall : KMP is preferred for DNA plagiarism detection due to its predictable performance and lower memory usage. The choice of algorithm should consider not only execution time but also factors like implementation complexity, memory usage, and the specific requirements of the application. So for DNA Plagiarism KMP is better than Robin-Karp algorithm

Algorithmic Metric 1 : Algorithm Efficiency

Rabin-Karp Algorithm: Rabin-Karp is efficient in handling multiple patterns simultaneously but can be slower due to the overhead of hash computation and collision checking, especially with large texts or when hash collisions occur.

KMP Algorithm: KMP is efficient because it avoids redundant comparisons by using the LPS (Longest Prefix Suffix) array. This makes it particularly suitable for longer patterns or texts where partial matches frequently occur.

Algorithmic Metric 2 : Time Complexity

Rabin-Karp has an average-case time complexity of O(n+m) and KMP has O(n), where n is the length of the text and m is the length of the pattern. However, real-world performance is influenced by many practical factors, like the overhead of hash calculations in Rabin-Karp or the memory access patterns in KMP.

Conclusion for DNA Plagiarism :

• Single Pattern Matching: KMP is highly efficient for single-pattern searches, which is typical in DNA sequence analysis where you’re looking for a specific sequence in a large genome.
• Predictable Performance: KMP avoids redundant comparisons by using the LPS (Longest Prefix Suffix) array, ensuring linear time complexity regardless of the input, which is crucial for processing long DNA sequences.
• Low Memory Usage: KMP’s minimal memory requirements make it ideal for large DNA datasets where memory efficiency is important.

Over all Comparison :