3 ms·

Is your question "How do you create an index that allows regexes?" In that case, I'd like to know the answer to the question, as well.

by drcode 17y ago

thwarted 17y ago
perl has a "study" function that examines a string in anticipation of doing many pattern matches on it. I'm not sure what it does exactly, but the kind of structures it creates could be serialized and stored along with an input file (or perhaps replace it), and used as kind of regular expression optimized index. This isn't necessarily an "index" in the normal sense, but then, neither is the likes of a full-text index either. But really, any data structures that are optimized for a specific kind of processing are indexes.
- jrockway 17y ago
  study does not do anything really interesting. It looks up substrings in a table of substring -> average frequency. It then scans for the rarest character first, so that it can fail quickly for most input. From the docs: (The way "study" works is this: a linked list of every character in the string to be searched is made, so we know, for example, where all the 'k' characters are. From each search string, the rarest character is selected, based on some static frequency tables constructed from some C programs and English text. Only those places that contain this "rarest" character are examined.) Basically, this is not what Google is doing for code search.
  - thwarted 17y ago
    Study doesn't do anything really interesting, but neither is creating a keyword index for a keyword based search all that interesting either. Considering that Google code search is not intended to search English (for which their regular search technology would most likely suffice for that) using regular expressions, then I agree that the naive study implementation you've quoted is, basically, not what Google is using for code search. However, there's no reason that the frequency tables need to be static nor need to be constructed solely from from C programs and English text. Frequency tables can be continuously updated based on the input corpus and the input corpus should be the code that is being searched. Part of search is being able to rule out significant portions of the search space in the name of getting positive results as fast as possible, so being able to fail quickly for most inputs (considering the example regular expression only returns three hits, it seems a wide majority don't match), a study-like implementation would appear to be a possibility.

Is your question "How do you create an index that allows regexes?" In that case, I'd like to know the answer to the question, as well.

by drcode 17y ago

Is your question "How do you create an index that allows regexes?" In that case, I'd like to know the answer to the question, as well.

thwarted 17y ago

perl has a "study" function that examines a string in anticipation of doing many pattern matches on it. I'm not sure what it does exactly, but the kind of structures it creates could be serialized and stored along with an input file (or perhaps replace it), and used as kind of regular expression optimized index. This isn't necessarily an "index" in the normal sense, but then, neither is the likes of a full-text index either. But really, any data structures that are optimized for a specific kind of processing are indexes.

jrockway 17y ago
study does not do anything really interesting. It looks up substrings in a table of substring -> average frequency. It then scans for the rarest character first, so that it can fail quickly for most input. From the docs: (The way "study" works is this: a linked list of every character in the string to be searched is made, so we know, for example, where all the 'k' characters are. From each search string, the rarest character is selected, based on some static frequency tables constructed from some C programs and English text. Only those places that contain this "rarest" character are examined.) Basically, this is not what Google is doing for code search.
- thwarted 17y ago
  Study doesn't do anything really interesting, but neither is creating a keyword index for a keyword based search all that interesting either. Considering that Google code search is not intended to search English (for which their regular search technology would most likely suffice for that) using regular expressions, then I agree that the naive study implementation you've quoted is, basically, not what Google is using for code search. However, there's no reason that the frequency tables need to be static nor need to be constructed solely from from C programs and English text. Frequency tables can be continuously updated based on the input corpus and the input corpus should be the code that is being searched. Part of search is being able to rule out significant portions of the search space in the name of getting positive results as fast as possible, so being able to fail quickly for most inputs (considering the example regular expression only returns three hits, it seems a wide majority don't match), a study-like implementation would appear to be a possibility.