Applications of a binary search engine based on an inverted index of byte sequences
Techniques for searching an inverted index associating byte sequences of a fixed length and files that contain those byte sequences are described herein. Byte sequences comprising a search query are determined and searched in the inverted index. In some examples, the inverted index may be distributed across multiple computers and the search may be performed in parallel. In some examples, a search query may be submitted as expressions comprising query language or regular expressions that are interpreted as search terms, transformed into byte sequences, and searched for in the inverted index. In some examples, an automatic notification request for a search query may be processed and notifications may be sent based on a default or preferred frequency and method.
1. A system comprising:
one or more processors; and
programming instructions configured to be executed by the one or more processors to perform operations including:
receiving an expression as a search query, the expression including at least one of a rule statement or one or more metacharacters, wherein the one or more metacharacters includes one or more characters defined with one or more specific functions;
interpreting the expression into one or more search terms;
determininq one or more target byte sequences of a fixed length that correspond to respective search terms of the one or more search terms;
searching for the one or more target byte sequences in an inverted index, wherein the inverted index maps a plurality of byte sequences of the fixed length to one or more file identifiers of files that include individual ones of the plurality of byte sequences;
evaluating results of the searching based on the expression; and
returning a search result to the search query based on the evaluating.
2. The system of claim 1 , wherein the expression includes the rule statement with one or more logical operators, and wherein the operations further comprise:
constructing a syntax tree from the one or more logical operators; and
evaluating the results using the syntax tree.
3. The system of claim 2 , wherein the operations further include constructing the syntax tree based on the one or more logical operators, wherein the one or more search terms are evaluated as leaves of the syntax tree, each leaf comprising one or more byte sequences associated with one of the one or more search terms.
4. The system of claim 1 , wherein the expression includes at least one metacharacter defining a grouping function, and wherein interpreting the expression into one or more search terms includes applying the grouping function to a text string portion of the expression.
5. The system of claim 1 , wherein the expression includes at least one metacharacter defining a search pattern function, and wherein interpreting the expression into one or more search terms includes applying the search pattern function to a text string portion of the expression.
6. The system of claim 1 , wherein the system includes a plurality of computing devices and the one or more processors, execution of the programming instructions, and inverted index are distributed across the plurality of computing devices.
7. The system of claim 1 , wherein the operations further include, before performing the returning, validating that a file corresponding to the search result satisfies the expression.
8. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
receiving an expression as a search query, the expression including at least one of a rule statement or one or more metacharacters, wherein the one or more metacharacters includes one or more characters defined with one or more specific functions;
interpreting the expression into one or more search terms;
determininq one or more target byte sequences of a fixed length that correspond to respective search terms of the one or more search terms;
searching for the one or more target byte sequences in an inverted index, wherein the inverted index maps a plurality of byte sequences of the fixed length to one or more file identifiers of files that include individual ones of the plurality of byte sequences;
evaluating results of the searching based on the expression; and
returning a search result to the search query based on the evaluating.
9. The one or more non-transitory computer readable media of claim 8 , wherein the expression includes the rule statement with one or more logical operators, and wherein the operations further comprise:
constructing a syntax tree from the one or more logical operators; and
evaluating the results using the syntax tree.
10. The one or more non-transitory computer readable media of claim 9 , wherein the operations further include constructing the syntax tree based on the one or more logical operators, wherein the one or more search terms are evaluated as leaves of the syntax tree, each leaf comprising one or more byte sequences associated with one of the one or more search terms.
11. The one or more non-transitory computer readable media of claim 8 , wherein the expression includes at least one metacharacter defining a grouping function, and wherein interpreting the expression into one or more search terms includes applying the grouping function to a text string portion of the expression.
12. The one or more non-transitory computer readable media of claim 8 , wherein the expression includes at least one metacharacter defining a search pattern function, and wherein interpreting the expression into one or more search terms includes applying the search pattern function to a text string portion of the expression.
13. The one or more non-transitory computer readable media of claim 8 , wherein a system includes a plurality of computing devices and the one or more processors, execution of the computer-executable instructions, and inverted index are distributed across the plurality of computing devices.
14. The one or more non-transitory computer readable media of claim 8 , wherein the operations further include, before performing the returning, validating that a file corresponding to the search result satisfies the expression.
15. A computer-implemented method comprising:
receiving an expression as a search query, the expression including at least one of a rule statement or one or more metacharacters, wherein the one or more metacharacters includes one or more characters defined with one or more specific functions;
interpreting the expression into one or more search terms;
determining one or more target byte sequences of a fixed length that correspond to respective search terms of the one or more search terms;
searching for the one or more target byte sequences in an inverted index, wherein the inverted index maps a plurality of byte sequences of the fixed length to one or more file identifiers of files that include individual ones of the plurality of byte sequences;
evaluating results of the searching based on the expression; and
returning a search result to the search query based on the evaluating.
16. The method of claim 15 , wherein the expression includes the rule statement with one or more logical operators, and wherein the method further comprises:
constructing a syntax tree from the one or more logical operators; and
evaluating the results using the syntax tree.
17. The method of claim 16 , wherein the method further comprises constructing the syntax tree based on the one or more logical operators, wherein the one or more search terms are evaluated as leaves of the syntax tree, each leaf comprising one or more byte sequences associated with one of the one or more search terms.
18. The method of claim 15 , wherein the expression includes at least one metacharacter defining a grouping function, and wherein interpreting the expression into one or more search terms includes applying the grouping function to a text string portion of the expression.
19. The method of claim 15 , wherein the expression includes at least one metacharacter defining a search pattern function, and wherein interpreting the expression into one or more search terms includes applying the search pattern function to a text string portion of the expression.
20. The method of claim 15 , wherein a plurality of computing devices comprising one or more processors execute of programming instructions to perform the method, and the inverted index is distributed across the plurality of computing devices.