# US 2018/0026652 A1 · Technologies for efficiently compressing data with multiple hash tables

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0026652 A1
- Document ID: US20180026652A1
- Status: Published application
- Kind: A1
- Application number: 15/638,842
- Filed: 2017-06-30
- Published: 2018-01-25
- Earliest claimed: 2016-07-22
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Daniel F. Cutter; Vinodh Gopal; James D. Guilford
- Web page: https://patentgrep.com/patent/US20180026652A1

## CPC

- G06F 3/061: {Improving I/O performance}
- G02B 6/3882: {using rods, pins or balls to align a pair of ferrule ends}
- G02B 6/3893: {Push-pull type, e.g. snap-in, push-on}
- G02B 6/3897: {Connectors fixed to housings, casing, frames or circuit boards (G02B6/44528 takes precedence)}
- G02B 6/4292: {the light guide being disconnectable from the opto-electronic element, e.g. mutually self aligning arrangements}
- G06F 1/183: Internal mounting support structures, e.g. for supporting printed circuit boards
- G06F 1/20: Cooling means
- G06F 3/0613: {in relation to throughput}
- G06F 3/0625: {Power saving in storage systems}
- G06F 3/064: {Management of blocks}
- G06F 3/065: {Replication mechanisms}
- G06F 3/0653: {Monitoring storage devices or systems}
- G06F 3/0655: {Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices}
- G06F 3/0664: {at device level, e.g. emulation of a storage device or system}
- G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes}
- G06F 3/0673: {Single storage device}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 3/0683: {Plurality of storage devices}
- G06F 3/0688: {Non-volatile semiconductor memory arrays}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- G06F 8/65: Updates (security arrangements therefor G06F21/57)
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/4401: Bootstrapping (security arrangements therefor G06F21/57)
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 9/544: {Buffers; Shared memory; Pipes}
- G06F 12/109: for multiple virtual address spaces, e.g. segmentation (G06F12/1036 takes precedence)
- G06F 12/1408: {by using cryptography (for digital transmission H04L9/00)}
- G06F 13/1668: {Details of memory controller}
- G06F 13/385: {for adaptation of a particular data processing system to different peripheral devices}
- G06F 13/4022: {using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence)}
- G06F 13/4068: {Electrical coupling}
- G06F 13/409: {Mechanical coupling (back panels H05K7/1438)}
- G06F 15/161: {Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning (casings, cabinets, racks or drawers for data centers H05K5/00)}
- G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)}
- G06F 16/9014: {hash tables}
- G08C 17/02: using a radio link
- G11C 5/02: Disposition of storage elements, e.g. in the form of a matrix array
- G11C 7/1072: {for memories with random access ports synchronised on clock signal pulse trains, e.g. synchronous memories, self timed memories}
- G11C 11/56: using storage elements with more than two stable states represented by steps, e.g. of voltage, current, phase, frequency
- G11C 14/0009: {in which the volatile element is a DRAM cell}
- H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method}
- H03M 7/3086: {employing a sliding window, e.g. LZ77}
- H03M 7/4056: {Coding table selection}
- H03M 7/4081: {Static prefix coding}
- H04B 10/25891: {Transmission components (H04B10/40 takes precedence)}
- H04L 41/145: {involving simulating, designing, planning or modelling of a network}
- H04L 43/0817: by checking functioning
- H04L 43/0876: Network utilisation, e.g. volume of load or congestion level
- H04L 43/0894: Packet rate
- H04L 47/83: based on usage prediction
- H04L 49/00: Packet switching elements
- H04L 49/25: Routing or path finding in a switch fabric
- H04L 49/35: Switches specially adapted for specific applications
- H04L 49/357: {Fibre channel switches}
- H04L 49/45: Arrangements for providing or supporting expansion
- H04L 67/02: based on web technology, e.g. hypertext transfer protocol [HTTP]
- H04L 67/306: User profiles
- H04L 69/04: Protocols for data compression, e.g. ROHC
- H04L 69/329: in the application layer [OSI layer 7]
- H04Q 1/09: {Frames or mounting racks not otherwise provided for}
- H04Q 11/0003: {Details}
- H05K 7/1442: {with a radial structure}
- B25J 15/0014: {having fork, comb or plate shaped means for engaging the lower surface on a object to be transported}
- B65G 1/0492: {with cars adapted to travel in storage aisles}
- G05D 23/1921: {using a thermal motor}
- G05D 23/2039: {using mechanical means}
- G06F 3/0611: {in relation to response time}
- G06F 3/0616: {in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/0638: {Organizing or formatting or addressing of data}
- G06F 3/0647: {Migration mechanisms}
- G06F 3/0658: {Controller construction arrangements}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]}
- G06F 9/5016: {the resource being the memory}
- G06F 9/5044: {considering hardware capabilities}
- G06F 9/505: {considering the load}
- G06F 9/5072: {Grid computing}
- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F 11/141: {for bus or memory accesses}
- G06F 11/3414: {Workload generation, e.g. scripts, playback}
- G06F 12/0862: with prefetch
- G06F 12/0893: Caches characterised by their organisation or structure
- G06F 12/10: Address translation
- G06F 13/161: {with latency improvement}
- G06F 13/1694: {Configuration of memory controller to different memory types}
- G06F 13/42: Bus transfer protocol, e.g. handshake; Synchronisation
- G06F 13/4282: {on a serial bus, e.g. I2C bus, SPI bus (on daisy chain buses G06F13/4247)}
- G06F 15/8061: {Details on data memory access}
- G06F 2209/483: Multiproc
- G06F 2209/5019: Workload prediction
- G06F 2209/5022: Workload threshold
- G06F 2212/1008: Correctness of operation, e.g. memory ordering
- G06F 2212/1024: Latency reduction
- G06F 2212/1041: Resource optimization
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/152: Virtualized environment, e.g. logically partitioned system
- G06F 2212/202: Non-volatile memory
- G06F 2212/401: Compressed data
- G06F 2212/402: Encrypted data
- G06F 2212/7207: management of metadata or control data
- G06Q 10/06: Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G06Q 10/06314: {Calendaring for a resource}
- G06Q 10/087: Inventory or stock management, e.g. order filling, procurement or balancing against orders
- G06Q 10/20: Administration of product repair or maintenance
- G06Q 50/04: Manufacturing
- G07C 5/008: {communicating information to a remotely located station (transmission systems for measured values G08C)}
- G08C 2200/00: Transmission systems for measured values, control or similar signals
- G11C 5/06: Arrangements for interconnecting storage elements electrically, e.g. by wiring
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M 7/4031: {Fixed length to variable length coding}
- H03M 7/6005: {Decoder aspects}
- H03M 7/6023: {Parallelization}
- H04B 10/25: Arrangements specific to fibre transmission
- H04J 14/00: Optical multiplex systems
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/3247: {involving digital signatures}
- H04L 9/3263: {involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements (network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823)}
- H04L 12/2809: {indicating that an appliance service is present in a home automation network (monitoring functionality H04L43/0817; discovery or management thereof, e.g. service location protocol [SLP] or web services, H04L67/51)}
- H04L 41/024: {using relational databases for representation of network management data, e.g. managing via structured query language [SQL]}
- H04L 41/046: comprising network management agents or mobile agents therefor
- H04L 41/0813: characterised by the conditions triggering a change of settings
- H04L 41/082: the condition being updates or upgrades of network functionality
- H04L 41/12: Discovery or management of network topologies
- H04L 41/149: for prediction of maintenance
- H04L 41/40: using virtualisation of network functions or resources, e.g. SDN or NFV entities
- H04L 41/5019: Ensuring fulfilment of SLA
- H04L 43/065: related to network devices
- H04L 43/16: Threshold monitoring
- H04L 45/02: Topology update or discovery
- H04L 45/52: Multiprotocol routers
- H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS
- H04L 47/38: by adapting coding or compression rate
- H04L 47/765: triggered by the end-points
- H04L 47/782: {Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities}
- H04L 47/805: {QOS or priority aware}
- H04L 47/82: {Miscellaneous aspects}
- H04L 49/15: Interconnection of switching modules
- H04L 49/555: {Error detection}
- H04L 61/00: Network arrangements, protocols or services for addressing or naming
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- H04L 67/1004: Server selection for load balancing
- H04L 67/1008: based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30)
- H04L 67/1012: based on compliance of requirements or conditions with available server resources
- H04L 67/1014: based on the content of a request
- H04L 67/1029: using data related to the state of servers by a load balancer
- H04L 67/1034: Reaction to server failures by a load balancer
- H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
- H04L 67/12: specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
- H04L 67/34: {involving the movement of software or configuration parameters (network booting or remote initial program loading [RIPL] G06F9/4416)}
- H04L 67/51: Discovery or management thereof, e.g. service location protocol [SLP] or web services
- H04Q 1/04: Frames or mounting racks for selector switches; Accessories therefor, e.g. frame cover
- H04Q 11/00: Selecting arrangements for multiplex systems (multiplex systems H04J)
- H04Q 11/0005: {Switch and router aspects}
- H04Q 11/0062: {Network aspects}
- H04Q 11/0071: {Provisions for the electrical-optical layer interface}
- H04Q 2011/0037: {Operation}
- H04Q 2011/0041: {Optical control}
- H04Q 2011/0052: {Interconnection of switches}
- H04Q 2011/0073: {Provisions for forwarding or routing, e.g. lookup tables}
- H04Q 2011/0079: {Operation or maintenance aspects}
- H04Q 2011/0086: {Network resource allocation, dimensioning or optimisation}
- H04Q 2213/13523: bandwidth management, e.g. capacity management
- H04Q 2213/13527: protocols - X.25, TCAP etc.
- H04W 4/023: {using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds}
- H04W 4/80: Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication
- H05K 1/0203: {Cooling of mounted components (H05K1/0272 takes precedence)}
- H05K 1/181: associated with surface mounted components
- H05K 5/0204: {Mounting supporting structures on the outside of casings}
- H05K 7/1418: {Card guides, e.g. grooves (H05K7/1425 takes precedence)}
- H05K 7/1421: {Drawers for printed circuit boards}
- H05K 7/1422: {Printed circuit boards receptacles, e.g. stacked structures, electronic circuit modules or box like frames}
- H05K 7/1447: {External wirings; Wiring ducts; Laying cables}
- H05K 7/1461: {Slidable card holders; Card stiffeners; Control or display means therefor}
- H05K 7/1485: {Servers; Data center rooms, e.g. 19-inch computer racks}
- H05K 7/1487: {Blade assemblies, e.g. blade cases or inner arrangements within a blade}
- H05K 7/1489: {characterized by the mounting of blades therein, e.g. brackets, rails, trays (H05K7/1491 takes precedence)}
- H05K 7/1491: {having cable management arrangements (management of optical cables G02B6/444; in telecommunication cabinets H04Q1/06)}
- H05K 7/1492: {having electrical distribution arrangements, e.g. power supply or data communications}
- H05K 7/1498: {Resource management, Optimisation arrangements, e.g. configuration, identification, tracking, physical location (thermal management H05K7/20836)}
- H05K 7/2039: {characterised by the heat transfer by conduction from the heat generating element to a dissipating body (arrangements for increasing/decreasing heat-transfer, e.g. fins details, F28F13/00)}
- H05K 7/20709: {for server racks or cabinets; for data centers, e.g. 19-inch computer racks}
- H05K 7/20727: {within server blades for removing heat from heat source}
- H05K 7/20736: {within cabinets for removing heat from server blades}
- H05K 7/20745: {within rooms for removing heat from cabinets, e.g. by air conditioning device}
- H05K 7/20836: {Thermal management, e.g. server temperature control}
- H05K 13/0486: {Replacement and removal of components}
- H05K 2201/066: Heatsink mounted on the surface of the printed circuit board [PCB]
- H05K 2201/10121: Optical component, e.g. opto-electronic component
- H05K 2201/10159: Memory
- H05K 2201/10189: Non-printed connector
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- Y02P 90/30: Computing systems specially adapted for manufacturing
- Y04S 10/50: Systems or methods supporting the power network operation or management, involving a certain degree of interaction with the load-side end user applications
- Y04S 10/52: Outage or fault management, e.g. fault detection or location
- Y10S 901/01: Mobile robot
- Y10S 901/30: End effector
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G02B: OPTICAL ELEMENTS, SYSTEMS OR APPARATUS
- G08C: TRANSMISSION SYSTEMS FOR MEASURED VALUES, CONTROL OR SIMILAR SIGNALS (fluid pressure transmitting systems F15B; mechanical means for transferring the output of a sensing member into a different variable G01D5/00; mechanical control systems G05G)
- G11C: STATIC STORES (semiconductor memory devices H10B)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04B: TRANSMISSION
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W)
- H05K: PRINTED CIRCUITS; CASINGS OR CONSTRUCTIONAL DETAILS OF ELECTRIC APPARATUS; MANUFACTURE OF ASSEMBLAGES OF ELECTRICAL COMPONENTS
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})
- B65G: TRANSPORT OR STORAGE DEVICES, e.g. CONVEYORS FOR LOADING OR TIPPING, SHOP CONVEYOR SYSTEMS OR PNEUMATIC TUBE CONVEYORS (packaging B65B; handling thin or filamentary materials, e.g. paper sheets or thread, B65H; cranes B66C; portable mobile or lifting or hauling appliances, e.g. hoists, B66D; devices for lifting or lowering goods for loading or unloading purposes, e.g. fork-lift trucks, B66F9/00; emptying bottles, jars, casks, barrels or similar containers, not otherwise provided for, B67C9/00; delivering or transferring liquids B67D; filling or discharging vessels for liquefied, solidified or compressed gases F17C; pipe-line systems for fluids F17D)
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G07C: TIME OR ATTENDANCE REGISTERS; REGISTERING OR INDICATING THE WORKING OF MACHINES; GENERATING RANDOM NUMBERS; VOTING OR LOTTERY APPARATUS; ARRANGEMENTS, SYSTEMS OR APPARATUS FOR CHECKING NOT PROVIDED FOR ELSEWHERE
- H04J: MULTIPLEX COMMUNICATION (transmission in general H04B; peculiar to transmission of digital information H04L5/00; systems for the simultaneous or sequential transmission of more than one television signal H04N7/08; in exchanges H04Q11/00; stereophonic systems H04S)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y04S: SYSTEMS INTEGRATING TECHNOLOGIES RELATED TO POWER NETWORK OPERATION, COMMUNICATION OR INFORMATION TECHNOLOGIES FOR IMPROVING THE ELECTRICAL POWER GENERATION, TRANSMISSION, DISTRIBUTION, MANAGEMENT OR USAGE, i.e. SMART GRIDS
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

Technologies for compressing data with multiple hash tables include a compute device. The compute device is to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash. Each string prefix defines a set of consecutive symbols in a string that starts at a present position in an input stream of symbols. The compute device is also to write, to a different hash table for each string prefix size, a pointer to the present position in association with the associated hash. Each hash is usable as an index into the associated hash table to provide the present position of the string.

## Claims

### Claim 1

A compute device comprising:
one or more processors; and
a memory having stored therein a plurality of instructions that, when executed by the one or more processors, cause the compute device to:
produce, for each of multiple string prefixes of different string prefix sizes, an associated hash, wherein each string prefix defines a set of consecutive symbols in a string that starts at a present position in an input stream of symbols; and
write, to a different hash table for each string prefix size, a pointer to the present position in association with the associated hash, wherein each hash is usable as an index into the associated hash table to provide the present position of the string.

### Claim 2 (depends on 1)

The compute device of claim 1, wherein the plurality of instructions, when executed, further cause the compute device to search, with the produced hashes as indexes into the associated hash tables and in an order based on the string prefix sizes associated with the hashes, for a string at a previous position in the input stream that matches the string at the present position.

### Claim 3 (depends on 2)

The compute device of claim 2, wherein the plurality of instructions, when executed, further cause the compute device to output, in response to an identification of a matched string, a reference to the matched string in a set of compressed output data.

### Claim 4 (depends on 2)

The compute device of claim 2, wherein the plurality of instructions, when executed, further cause the compute device to output, in response to a determination that a matched string has not been identified, the symbol at the present position to a set of compressed output data.

### Claim 5 (depends on 2)

The compute device of claim 2, wherein to search for a string at a previous position that matches the string at the present position comprises to:
obtain a chain of pointers from one or more of the hash tables; and
compare the string referenced by each pointer in the chain of pointers to the string at the present position in the input stream.

### Claim 6 (depends on 5)

The compute device of claim 5, wherein to obtain the chain of pointers comprises to obtain a chain of pointers that are ordered as a function of the associated string prefix sizes on which the associated hashes are based.

### Claim 7 (depends on 3)

The compute device of claim 3, wherein the plurality of instructions, when executed, further cause the compute device to select, in response to a determination that multiple strings match the string at the present position, the longest matched string as the result of the search.

### Claim 8 (depends on 1)

The compute device of claim 1, wherein to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash comprises to produce a hash for each of a string prefix size of five symbols, a string prefix size of four symbols, and a string prefix size of three symbols.

### Claim 9 (depends on 1)

The compute device of claim 1, wherein to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash comprises to produce a hash for each of a string prefix size of five bytes, a string prefix size of four bytes, and a string prefix size of three bytes.

### Claim 10 (depends on 1)

The compute device of claim 1, wherein to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash comprises to produce a hash in which a lower subset of bits in the hash defines an identifier of a bank and a remainder of the bits in the hash define an index into the bank.

### Claim 11 (depends on 1)

The compute device of claim 1, wherein to write, to a different hash table for each string prefix size, a pointer to the present position comprises to write a pointer to the present position to a first hash table for hashes based on string prefixes of five symbols, a second hash table for hashes based on string prefixes of four symbols, and a third hash table for hashes based on string prefixes of three symbols.

### Claim 12 (depends on 11)

The compute device of claim 11, wherein to write a pointer to the first hash table comprises to evict one or more pointers from the first hash table to a spill table before the pointer to the present position is written to the first hash table.

### Claim 13

One or more machine-readable storage media comprising a plurality of instructions stored thereon that, when executed by a compute device cause the compute device to:
produce, for each of multiple string prefixes of different string prefix sizes, an associated hash, wherein each string prefix defines a set of consecutive symbols in a string that starts at a present position in an input stream of symbols; and
write, to a different hash table for each string prefix size, a pointer to the present position in association with the associated hash, wherein each hash is usable as an index into the associated hash table to provide the present position of the string.

### Claim 14 (depends on 13)

The one or more machine-readable storage media of claim 13, wherein the plurality of instructions, when executed, further cause the compute device to search, with the produced hashes as indexes into the associated hash tables and in an order based on the string prefix sizes associated with the hashes, for a string at a previous position in the input stream that matches the string at the present position.

### Claim 15 (depends on 14)

The one or more machine-readable storage media of claim 14, wherein the plurality of instructions, when executed, further cause the compute device to output, in response to an identification of a matched string, a reference to the matched string in a set of compressed output data.

### Claim 16 (depends on 14)

The one or more machine-readable storage media of claim 14, wherein the plurality of instructions, when executed, further cause the compute device to output, in response to a determination that a matched string has not been identified, the symbol at the present position to a set of compressed output data.

### Claim 17 (depends on 14)

The one or more machine-readable storage media of claim 14, wherein to search for a string at a previous position that matches the string at the present position comprises to:
obtain a chain of pointers from one or more of the hash tables; and
compare the string referenced by each pointer in the chain of pointers to the string at the present position in the input stream.

### Claim 18 (depends on 17)

The one or more machine-readable storage media of claim 17, wherein to obtain the chain of pointers comprises to obtain a chain of pointers that are ordered as a function of the associated string prefix sizes on which the associated hashes are based.

### Claim 19 (depends on 15)

The one or more machine-readable storage media of claim 15, wherein the plurality of instructions, when executed, further cause the compute device to select, in response to a determination that multiple strings match the string at the present position, the longest matched string as the result of the search.

### Claim 20 (depends on 13)

The one or more machine-readable storage media of claim 13, wherein to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash comprises to produce a hash for each of a string prefix size of five symbols, a string prefix size of four symbols, and a string prefix size of three symbols.

### Claim 21 (depends on 13)

The one or more machine-readable storage media of claim 13, wherein to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash comprises to produce a hash for each of a string prefix size of five bytes, a string prefix size of four bytes, and a string prefix size of three bytes.

### Claim 22 (depends on 13)

The one or more machine-readable storage media of claim 13, wherein to produce, for each of multiple string prefixes of different string prefix sizes, an associated hash comprises to produce a hash in which a lower subset of bits in the hash defines an identifier of a bank and a remainder of the bits in the hash define an index into the bank.

### Claim 23 (depends on 13)

The one or more machine-readable storage media of claim 13, wherein to write, to a different hash table for each string prefix size, a pointer to the present position comprises to write a pointer to the present position to a first hash table for hashes based on string prefixes of five symbols, a second hash table for hashes based on string prefixes of four symbols, and a third hash table for hashes based on string prefixes of three symbols.

### Claim 24

A method for compressing data with multiple hash tables, the method comprising:
producing, by a compute device and for each of multiple string prefixes of different string prefix sizes, an associated hash, wherein each string prefix defines a set of consecutive symbols in a string that starts at a present position in an input stream of symbols; and
writing, by the compute device and to a different hash table for each string prefix size, a pointer to the present position in association with the associated hash, wherein each hash is usable as an index into the associated hash table to provide the present position of the string.

### Claim 25 (depends on 24)

The method of claim 24, further comprising searching, by the compute device and with the produced hashes as indexes into the associated hash tables and in an order based on the string prefix sizes associated with the hashes, for a string at a previous position in the input stream that matches the string at the present position.