3 ms·

Something like this? - Regular expression searching on compressed text, http://portal.acm.org/citation.cfm?id=967612 http://portal.acm.org/citation.cfm?id=9676

by crux_ 17y ago

Something like this? - Regular expression searching on compressed text, http://portal.acm.org/citation.cfm?id=967612 http://portal.acm.org/citation.cfm?id=967612

mbrubeck 17y ago
The cost of that algorithm still grows linearly with respect to the length of the compressed text. It's possible Google is doing something like this (searching over the entire corpus until they find a match), but is there any work on precomputing an actual "index" to speed up this type of search?
- crux_ 17y ago
  I'm certain there are many approaches to be found via citation-following. But consider that you can use the linked algorithm, and a bit of trickiness, to create an index already: - Step (a): prepare another version of the document where every digit is replaced with 0, every word char with 'a', etc. - Step (b): note how much better it compresses. :) - Step (c): Perform a similar 'weakening' on the search regex. - Step (d): Done! Not an exact index, but it will allow you to quickly eliminate a large number of documents. You can also combine this approach with text-based ones for the cases where there are parts of the search regex that contain literal text. (This is almost certainly the most common use case). Or you could make it hierarchical if you need to by creating several watered-down texts for each input with different levels of substitution. --------------------------------------------------- Since this is the sort of thing that's fun to think about, here's a whole different approach: - Break each document apart into code lines. - Create a hierarchical tree: leaves are the code snippets (with a pointer back to source doc), each node represents a clustering-by-text-similarity of all its children. (Appropriate distance measure left as an exercise for the reader. :) ) - Let's say that for two regular expressions, RA & RB, RA < RB iff any text matched by RA will also be matched by RB. - At each node, create a regular expression R so that for each child regex C, C < R. (The leaves become a regex that simply matches the source line literally.) Along the way, make a best effort to restrict the length of R by introducing generalizations (R can't simply be Ca|Cb|Cc...) without making it so loose that it matches everything. - Then, searching for a regex S can be done recursively: For each child regex R of the current node, if you can construct a new regex T such that T < S and T < R, descend into that node. n.b. I typed that out in a hurry and without being rigorous... so it's probably not quite right, but an interesting path to think about exploring. Also: testing if one regex is less than another (as defined above) is actually fairly straightforward, even though it seems hard. (And a quick edit to add: the last step is definitely wrong. Unfortunately I need to hop onto a conference call, so it'll have to wait until the indefinite future.) (Edit to that: I think I fixed it for now. Shorter version: if the intersection of S and R is nonempty, descend.)
  - crux_ 17y ago
    Replying to myself, since editing was getting out of control. A neat property of the 2nd approach is that if you ever reach a node R where R < S you're done: all children will be matched. A less neat property is that it won't allow multi-line matches, but I'm not sure those are allowed anyway.

by crux_ 17y ago

Something like this? - Regular expression searching on compressed text, http://portal.acm.org/citation.cfm?id=967612 http://portal.acm.org/citation.cfm?id=967612

mbrubeck 17y ago

The cost of that algorithm still grows linearly with respect to the length of the compressed text. It's possible Google is doing something like this (searching over the entire corpus until they find a match), but is there any work on precomputing an actual "index" to speed up this type of search?

crux_ 17y ago
I'm certain there are many approaches to be found via citation-following. But consider that you can use the linked algorithm, and a bit of trickiness, to create an index already: - Step (a): prepare another version of the document where every digit is replaced with 0, every word char with 'a', etc. - Step (b): note how much better it compresses. :) - Step (c): Perform a similar 'weakening' on the search regex. - Step (d): Done! Not an exact index, but it will allow you to quickly eliminate a large number of documents. You can also combine this approach with text-based ones for the cases where there are parts of the search regex that contain literal text. (This is almost certainly the most common use case). Or you could make it hierarchical if you need to by creating several watered-down texts for each input with different levels of substitution. --------------------------------------------------- Since this is the sort of thing that's fun to think about, here's a whole different approach: - Break each document apart into code lines. - Create a hierarchical tree: leaves are the code snippets (with a pointer back to source doc), each node represents a clustering-by-text-similarity of all its children. (Appropriate distance measure left as an exercise for the reader. :) ) - Let's say that for two regular expressions, RA & RB, RA < RB iff any text matched by RA will also be matched by RB. - At each node, create a regular expression R so that for each child regex C, C < R. (The leaves become a regex that simply matches the source line literally.) Along the way, make a best effort to restrict the length of R by introducing generalizations (R can't simply be Ca|Cb|Cc...) without making it so loose that it matches everything. - Then, searching for a regex S can be done recursively: For each child regex R of the current node, if you can construct a new regex T such that T < S and T < R, descend into that node. n.b. I typed that out in a hurry and without being rigorous... so it's probably not quite right, but an interesting path to think about exploring. Also: testing if one regex is less than another (as defined above) is actually fairly straightforward, even though it seems hard. (And a quick edit to add: the last step is definitely wrong. Unfortunately I need to hop onto a conference call, so it'll have to wait until the indefinite future.) (Edit to that: I think I fixed it for now. Shorter version: if the intersection of S and R is nonempty, descend.)
- crux_ 17y ago
  Replying to myself, since editing was getting out of control. A neat property of the 2nd approach is that if you ever reach a node R where R < S you're done: all children will be matched. A less neat property is that it won't allow multi-line matches, but I'm not sure those are allowed anyway.