Input enhancement (computer science): Difference between revisions

Revision as of 12:09, 20 December 2019

Latest revision as of 20:02, 1 November 2023

(3 intermediate revisions by 2 users 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 36 ⟶ 34:

=== In trees ===

Creating data structures to more efficiently search through data is also a form of input enhancement. Placing data into a tree to store and search through inputs is another popular technique. [[Tree (data structure)|Trees]] are used throughout computer science and many different types of trees -{{snd}} [[binary search treestree]]s, [[AVL treestree]]s, [[red-blackred–black treestree]]s, and [[2-32–3 tree]]s to name just a small few -{{snd}} have been developed to properly store, access, and manipulate data while maintaining their structure. Trees are a principal data structure for dictionary implementation.

The benefits of putting data in a tree are great, especially if the data is being manipulated or repeatedly searched through. Binary search trees are the most simplest, yet most common type of tree for this implementation. The insertion, deletion, and searching of items in a tree are all worst case O(''n''), but are most often executed in O(log ''n''). This makes the repeated searching of elements even quicker for large inputs. There are many different types of binary search trees that work more efficiently and even self-balance upon addition and removal of items, like the AVL tree which has a worst case O(log ''n'') for all searching, inserting, and deletion.

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-MooreBoyer–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.