Difference between revisions of "Preprocessing and postprocessing"
(Created page with "''For the component of the C programming language, see C preprocessor.'' Sometimes, it is necessary to perform relatively trivial modifications of the input, known as '''pre...") |
m (precomputation) |
||
| Line 5: | Line 5: | ||
In other cases, preprocessing is required because the algorithm is easier to implement when its input is a kind of "special case", but the general case may easily be reduced to it. For example, the stack-based algorithm for the [[all nearest smaller values]] problem can be simplified by introducing a sentinel value at the beginning of the list that is smaller than all other elements; this makes it unnecessary to check whether the stack ever becomes empty, and naturally allows recovery of the elements in the list with no preceding smaller value. This effectively reduces the general case to the specific case in which the first element in the list is the smallest one. | In other cases, preprocessing is required because the algorithm is easier to implement when its input is a kind of "special case", but the general case may easily be reduced to it. For example, the stack-based algorithm for the [[all nearest smaller values]] problem can be simplified by introducing a sentinel value at the beginning of the list that is smaller than all other elements; this makes it unnecessary to check whether the stack ever becomes empty, and naturally allows recovery of the elements in the list with no preceding smaller value. This effectively reduces the general case to the specific case in which the first element in the list is the smallest one. | ||
| − | More frequently, the data contained in the input must be reorganized and rehashed into a more useful form, that is, a form that will make the algorithm more efficient, or that is essential to the correct functioning of the algorithm itself. Some of these modifications are again quite trivial; for example, in ACM-style problems, input will often contain names of imaginary people, each of whom has a certain amount of money, or something like that; it is usually more convenient to assign the people unique consecutive integer IDs starting from zero, rather than to work with their names. Other modifications are less trivial conceptually; for example, many problems involving arrays of numbers are more easily solved by using the [[prefix sum array]] rather than the given array itself; this is often the case because the algorithm requires frequently computing the sums of segments of the array. A great many algorithms require their input to be sorted. In the [[Knuth–Morris–Pratt algorithm]], the preprocessing of the needle is the most difficult step; it augments the needle with information about how it matches shifts of itself. Likewise, constructing the [[suffix tree]] of a string is a form of preprocessing, which is very difficult to do efficiently. | + | More frequently, the data contained in the input must be reorganized and rehashed into a more useful form, that is, a form that will make the algorithm more efficient, or that is essential to the correct functioning of the algorithm itself. Some of these modifications are again quite trivial; for example, in ACM-style problems, input will often contain names of imaginary people, each of whom has a certain amount of money, or something like that; it is usually more convenient to assign the people unique consecutive integer IDs starting from zero, rather than to work with their names. Other modifications are less trivial conceptually, and are often known as '''precomputation'''; for example, many problems involving arrays of numbers are more easily solved by using the [[prefix sum array]] rather than the given array itself; this is often the case because the algorithm requires frequently computing the sums of segments of the array. A great many algorithms require their input to be sorted. In the [[Knuth–Morris–Pratt algorithm]], the preprocessing of the needle is the most difficult step; it augments the needle with information about how it matches shifts of itself. Likewise, constructing the [[suffix tree]] of a string is a form of preprocessing, which is very difficult to do efficiently. |
Occasionally, the output of an algorithm may have to undergo '''postprocessing'''. An obvious example is that if the input consists of names, and we decide to work with numerical IDs instead, and names are expected to appear in output, then we must convert the output of our algorithm from numerical IDs to names before we can print our output. Often, the output is expected to be sorted, even if the input was not. Sometimes, duplicate data points are expected to be removed, and we might have the option of doing this either in the preprocessing stage or the postprocessing stage. | Occasionally, the output of an algorithm may have to undergo '''postprocessing'''. An obvious example is that if the input consists of names, and we decide to work with numerical IDs instead, and names are expected to appear in output, then we must convert the output of our algorithm from numerical IDs to names before we can print our output. Often, the output is expected to be sorted, even if the input was not. Sometimes, duplicate data points are expected to be removed, and we might have the option of doing this either in the preprocessing stage or the postprocessing stage. | ||
Latest revision as of 03:38, 21 November 2011
For the component of the C programming language, see C preprocessor.
Sometimes, it is necessary to perform relatively trivial modifications of the input, known as preprocessing, to a program before it can be passed to the main algorithm. (Extremely trivial modifications, such as converting degrees to radians, are usually given little thought, and will not be discussed here.) Often, one will want to do this because the algorithm itself is easier to implement under the assumption that certain "tricky" cases will not be fed into it (because the preprocessing stage eliminates them). Forgetting that such cases exist is a common cause of error in implementing solutions to problems. This is often true for graph-theoretic algorithms that expect adjacency matrix input. For example, when performing Dijkstra's algorithm using an adjacency matrix as input, if there are multiple edges between a given pair of nodes, then the shortest edge should be selected and its weight placed into the adjacency matrix; on the other hand, if the graph is a flow network, then the edge weights, representing capacities, should be added; and if the graph represents a resistor network, with edge weights resistances, then the final entry should be the reciprocal of the sum of the reciprocals of the weights of the individual edges.
In other cases, preprocessing is required because the algorithm is easier to implement when its input is a kind of "special case", but the general case may easily be reduced to it. For example, the stack-based algorithm for the all nearest smaller values problem can be simplified by introducing a sentinel value at the beginning of the list that is smaller than all other elements; this makes it unnecessary to check whether the stack ever becomes empty, and naturally allows recovery of the elements in the list with no preceding smaller value. This effectively reduces the general case to the specific case in which the first element in the list is the smallest one.
More frequently, the data contained in the input must be reorganized and rehashed into a more useful form, that is, a form that will make the algorithm more efficient, or that is essential to the correct functioning of the algorithm itself. Some of these modifications are again quite trivial; for example, in ACM-style problems, input will often contain names of imaginary people, each of whom has a certain amount of money, or something like that; it is usually more convenient to assign the people unique consecutive integer IDs starting from zero, rather than to work with their names. Other modifications are less trivial conceptually, and are often known as precomputation; for example, many problems involving arrays of numbers are more easily solved by using the prefix sum array rather than the given array itself; this is often the case because the algorithm requires frequently computing the sums of segments of the array. A great many algorithms require their input to be sorted. In the Knuth–Morris–Pratt algorithm, the preprocessing of the needle is the most difficult step; it augments the needle with information about how it matches shifts of itself. Likewise, constructing the suffix tree of a string is a form of preprocessing, which is very difficult to do efficiently.
Occasionally, the output of an algorithm may have to undergo postprocessing. An obvious example is that if the input consists of names, and we decide to work with numerical IDs instead, and names are expected to appear in output, then we must convert the output of our algorithm from numerical IDs to names before we can print our output. Often, the output is expected to be sorted, even if the input was not. Sometimes, duplicate data points are expected to be removed, and we might have the option of doing this either in the preprocessing stage or the postprocessing stage.
