Input enhancement (computer science): Difference between revisions

Revision as of 10:47, 11 September 2023

Latest revision as of 20:02, 1 November 2023

(One intermediate revision by one other user not shown)

Line 1:

{{Orphan|date=January 2016}}

In [[computer science]], '''input enhancement''' is the principle that processing a given input to a problem and altering it in a specific way will increase [[Time complexity|runtime efficiency]] or [[DSPACE|space efficiency]], or both. The altered input is usually stored and accessed to simplify the problem. By exploiting the structure and properties of the inputs, input enhancement creates various speed-ups in the efficiency of the [[algorithm]].

Line 50 ⟶ 48:

This algorithm is extremely inefficient. The maximum number of check trials would be ''m''-''n''+1 trials, making the big-O efficiency at worst case O(''mn''). On average case, the maximum number of check trials would never be reached and only a few would be executed, resulting in an average time efficiency of O(''m''+''n'').

Because of the necessity of more efficient string matching algorithms, several faster algorithms have been developed, with most of them utilizing the idea of input enhancement. The key is preprocessed to gather information about what to look for in the text and that information is stored in order to refer back to them when necessary. The accessing of this information is constant time and greatly increases the runtime efficiency of the algorithms that use it, most famously the [[Knuth-Morris-PrattKnuth–Morris–Pratt algorithm]] algorithm and the [[Boyer–Moore string-search algorithm|Boyer-MooreBoyer–Moore algorithm]] algorithm. These algorithms, for the most part, use the same methods to obtain its efficiency with the main difference being on how the key is composed.

=== Horspool's algorithm ===

As a demonstration of input enhancement in string matching, one should examine a simplified version of the Boyer-Moore algorithm, [[Boyer–Moore–Horspool algorithm|Horspool's]] algorithm. The algorithm starts at the ''n''th character of the text ''m'' and compares the character. Let's call this character ''x''. There are 4 possible cases of what can happen next.