Data processing: vehicles – navigation – and relative location – Navigation
Reexamination Certificate
2002-10-11
2004-08-24
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
C341S065000
Reexamination Certificate
active
06782318
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data compression, and in particular to systems and methods for compressing text and data in a PDA.
BACKGROUND OF THE INVENTION
Navigational devices are well known. The capabilities of navigational devices and methods depend on system resources, such as processor speed and the amount and speed of memory. The processes implemented by a navigation device are a function of overall system cost because an increase in system capability also increases system cost. The known art includes a spectrum of products in which the degree of navigational accuracy is dictated primarily by the cost of the system. The lower cost systems currently offer a lower degree of accuracy that often is inadequate for most users. Other devices also depend on system resources, such as processor speed and the amount and speed of memory.
The known art compresses data, including text, in an attempt to improve the efficiency of the system resources. That is, compression improves the performance of a system that has a limited processor speed and a limited amount and speed of memory. Compressing data involves encoding data, and this encoded data is decoded for an end use in a device. For example, a navigational device end use includes, but is not limited to, displaying text or other cartographic data. One conventional method for encoding and decoding data, particularly text data, involves Huffman codes or canonical Huffman codes. Huffman codes and canonical Huffman codes will be described in more detail below.
Decoding the encoded data often involves a time-space tradeoff. Increasing the allocated space for a decoding structure typically increases the speed of the decoding operation; whereas decreasing the allocated space for a decoding structure often decreases the speed of the decoding operation. In certain applications, it is desired to balance the competing needs of decoding speed and memory space so that an adequate decoding speed is achieved using an acceptable amount of memory. For example, in certain applications, it may be desired to reduce the memory space taken up by the decoding structure at the expense of an acceptable slowing of the decoding speed. In other applications, it may be desired to increase the speed of the decoding operation at the expense of an acceptable amount of additional memory space taken up by the decoding structure.
Therefore, there exists a need for a data compression system and method which provides design flexibility by allowing design choices to be made to increase decoding speed by adding more space to the decoding structure or to decrease the decoding structure space and decrease the decoding speed.
SUMMARY OF THE INVENTION
The above mentioned problems of navigational devices are addressed by the present invention and will be understood by reading and studying the following specification. Systems and methods are provided to compress data, and in particular to code and decode data using canonical Huffman codes. These systems and methods are incorporated into navigational devices in one embodiment. However, the invention is not so limited.
An acceleration table is provided to extract high-frequency data using a direct index lookup and bracketing indices to provide bounds for a secondary search. In one embodiment, the secondary search is a binary search. A binary search table is provided to extract base canonical Huffman codes for each bit length of the encoded data, from which low-frequency data indices are derived to extract low-frequency data. Thus, the present invention provides design flexibility by allowing choices to be made with respect to balancing the competing needs of space and speed by, for example, increasing decoding speed by adding more space to the acceleration table in the decoding structure or decreasing the decoding structure space to conserve memory space at the expense of decreasing the decoding speed by an acceptable amount. A faster decoding speed allows a navigation device that has a limited processor and memory speed to provide more navigation data to a user in a timely manner. A smaller decoding structure allows more memory in a limited memory navigation device to be allocated for other purposes.
One aspect provides a data structure stored on a computer readable medium. According to one embodiment, the data structure includes a field representing a decoding structure to decode canonical Huffman encoded data, and a field representing a symbol table. The decoding structure includes a field representing an accelerator table to receive N bits from the encoded data to perform a 2
N
-deep direct-index lookup to provide a high-frequency symbol index for high-frequency data and to provide bracketing indices for low-frequency data. The decoding structure also includes a field representing a binary search table to provide a low-frequency symbol index using a binary search bounded by the bracketing indices provided by the accelerator table. The symbol table is adapted to provide a high-frequency symbol associated with the high-frequency index and a low-frequency symbol associated with the low-frequency symbol index.
Other aspects provided herein include an electronic navigational device, a navigation system, and a method for decoding encoded data. These, as well as other novel aspects, embodiments, advantages, details, and features of the present invention, will be apparent to those skilled in the art from the following detailed description of the invention, the attached claims and accompanying drawings, listed herein below, which are useful in explaining the invention.
REFERENCES:
patent: 3883847 (1975-05-01), Frank
patent: 5208593 (1993-05-01), Tong et al.
patent: 5821887 (1998-10-01), Zhu
patent: 6021406 (2000-02-01), Kuznetsov
patent: 6047280 (2000-04-01), Ashby et al.
patent: 6219457 (2001-04-01), Potu
patent: 6249744 (2001-06-01), Morita
patent: 6317684 (2001-11-01), Roeseler
patent: 6317687 (2001-11-01), Morimoto
patent: 6321158 (2001-11-01), DeLorme
patent: 6388877 (2002-05-01), Canova et al.
patent: 6393149 (2002-05-01), Friederich et al.
patent: 6430498 (2002-08-01), Maruyama et al.
patent: 6504496 (2003-01-01), Mesarovic et al.
patent: 6526351 (2003-02-01), Whitham
patent: 6563440 (2003-05-01), Kangas
patent: 2002/0038316 (2002-03-01), Onyon et al.
patent: 2003/0006918 (2003-01-01), Barnett
“An Optical pathfinder for vehicles in real-world digital terrain maps”, http:/www.nease.net/jamsoft//shortestpath/pathfiner/4.html, 11 pages, (1999).
“Informed Search Methods”,Artificial Intelligence, A Modern Approach Prentice-Hall, Inc., (1995),92-115.
“Real-Time Vehicle Routing in Dynamic Stochastic Urban Traffic Netowrks”, http:/www.gpu.srv.ualberta.ca/lfu/research.htm, (1997),1-3.
Ahuja, R.., “Faster Algorithms for the Shortest Path Problem”,Journal of the Association for Computing Machinery, 37(2), (1990),pp. 213-223.
Cung, V., et al., “An Efficient Implementation of Parallel A*”,CFPAR, Montreal, Canada,(1994),pp. 153-167.
Fredman, M., “Fibonacci heaps and their uses in improved network optimization algorithms”,Journal of ACM, (1987),2 pages.
Fu, L.., “Heuristic Shortest Path Algorithms and their Potential IVHS Applications”,Proceedings of the 4th UNiversity of Alberta—University of Calgary, Joint Graduate Student Symposium in Transportation Engineering, (1995),pp. 83-109.
Ikeda, T., “A Fast Algorithm for Finding Better Routes by Al Search Techniques”,Vehicle Navigation and Information Systems Conference Proceedings, (1994),pp. 291-296.
Kaindl, H., “Memory-Bounded Bidirectional Search”,Proceedings of the 12th National Conference on Art, AAAI Press, Seattle WA,(1994),pp. 1359-1364.
Laporte, G., “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms”,European Journal of Operational Research, 59,(1992),pp. 345-358.
Myers, B., “Data Structures for Best-First Search”, http://www.4.ncsu.edu/jbmyers/dsai.htm, (1997),pp. 1-6.
Ronngren, R., et al., “Parallel and Sequential Priority Queue Algorithms”,ACM Transactions on Modeling and Computer Simulation, (1997),pp. 168-172, 198,
Beesley Darin J.
Childs Michael E.
Liu Chunyen
Robinson Stephen C.
LandOfFree
System and method for compressing data in a PDA does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for compressing data in a PDA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for compressing data in a PDA will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287822