You can use PEXT alone without even messing with SIMD as long as there's enough good distinguishing bits in the early (first/last 8) parts of the string. The only thing that complicates this is that, as in the example in the article, sometimes some strings are proper prefixes/suffixes of others (which one is problematic depends on which direction you're using).
But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String.... Referenced Hacker's Delight when I was working on it. Granted, this was just for compressing the USHORT lengths into BYTE-sized lengths.
Are you sure your compression suggestion would work for prefix matches? If you can get lower latency than the fastest assembly version, I'm all ears: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri...
All of the compress/expand routines mentioned in that Hacker's Delight section you're quoting seem to mention upwards of 160+ instructions. My negative match logic fast-path only requires 12 instructions.
I called it Hanov after http://stevehanov.ca/blog/index.php?id=119 Problem is there that you have to calc a hash for each string, which is only fast with __builtin_crc/_mm_crc32_u64
Source: 11 years of string matching work. :-) We built a multiple hash table string matcher in the early days of Hyperscan (it's gone now).
Strings (written right to left):
-----101
--100101
-----010
--100010
Mask: 00111010
Table: Index Contents
0000 -----101
0001 -----010
0010 -----101
0011 -----010
0100 -----101
0101 -----010
0110 -----101
0111 -----010
1000 --100101
1001 --100010
1010 -----101
1011 -----010
1100 -----101
1101 -----010
1110 -----101
1111 -----010
Suppose the input is --101101After the mask, the result is 00101000
After the compress, the result is 1010
Table index 1010 has -----101, so it's a hit. with string 101.
Now Suppose the input is --100101
After the mask, the result is 00100000
After the compress, the result is 1000
Table index 1000 has --100101, so it's a hit. with string 100101.
I also can't see how you'd get that negative match fast path performance if you were reliant on hashes. That owes its speed to the length and unique char filter working in concert.
Find a 128-bit mask that will be used to select bits of the input string. You want to minimize the number of 1 bits in the mask, since the table size is 2^(number of 1 bits). On the other hand, you need to pick enough 1 bits so that there is only one string per table entry.
AND this mask with the input string. COMPRESS these bits using the mask. The result is the index into the table. Each entry has a string to compare and thermometer coded mask (number of 1 bits equals length of string in bits). AND the input string with the thermometer coded mask and compare it with the string. If they match, you have a hit.
COMPRESS (or generalized extract) means to move selected bits to the right so that they are all next to each other and adjacent to the LSB. There is a clever algorithm for this, see section 7-4 of Hacker's Delight:
https://doc.lagout.org/security/Hackers%20Delight.pdf