Java Reference
In-Depth Information
and the total number of comparisons required is 54.
Finally, if the list is organized by the transpose heuristic, then the final
list will be
A B F D G E C H;
and the total number of comparisons required is 62.
While self-organizing lists do not generally perform as well as search trees or a
sorted list, both of which require O(log n) search time, there are many situations in
which self-organizing lists prove a valuable tool. Obviously they have an advantage
over sorted lists in that they need not be sorted. This means that the cost to insert
a new record is low, which could more than make up for the higher search cost
when insertions are frequent. Self-organizing lists are simpler to implement than
search trees and are likely to be more efficient for small lists. Nor do they require
additional space. Finally, in the case of an application where sequential search is
“almost” fast enough, changing an unsorted list to a self-organizing list might speed
the application enough at a minor cost in additional code.
As an example of applying self-organizing lists, consider an algorithm for com-
pressing and transmitting messages. The list is self-organized by the move-to-front
rule. Transmission is in the form of words and numbers, by the following rules:
1. If the word has been seen before, transmit the current position of the word in
the list. Move the word to the front of the list.
2. If the word is seen for the first time, transmit the word. Place the word at the
front of the list.
Both the sender and the receiver keep track of the position of words in the list
in the same way (using the move-to-front rule), so they agree on the meaning of
the numbers that encode repeated occurrences of words. Consider the following
example message to be transmitted (for simplicity, ignore case in letters).
The car on the left hit the car I left.
The first three words have not been seen before, so they must be sent as full
words. The fourth word is the second appearance of “the,” which at this point is
the third word in the list. Thus, we only need to transmit the position value “3.”
The next two words have not yet been seen, so must be sent as full words. The
seventh word is the third appearance of “the,” which coincidentally is again in the
third position. The eighth word is the second appearance of “car,” which is now in
the fifth position of the list. “I” is a new word, and the last word “left” is now in
the fifth position. Thus the entire transmission would be
The car on 3 left hit 3 5 I 5.
Search WWH ::




Custom Search