Feature Proposition: "Boolean" advSearch Mode

Hello coroico,

While continuing to work with AjaxSearch and reviewing the advSearch options, I’ve really liked the speed and document control offered to the implementer, however I’d like to offer the user the ability to search more extensively than what I choose for them via advSearch. I think it may be interesting and beneficial to give the user more control over the searching process. The following proposition involves a new "boolean" search mode for advSearch which would offer additional flexibility to the searcher.


---


--- BOOLEAN ADVSEARCH MODE ---

(NOTE: What follows is absolutely not for a live search. Due to parsing issues, this shouldn’t be allowed to run until the entire search term has been submitted.)

A boolean search would give the search user a greater degree of control over what they are looking for. This dicussion is about collecting search terms and classifying them for search purposes, not the actual algorithm used to then search for the terms. What this will allow is permit multiple searches (oneword, allwords, exactphrase, etc.) to be performed on a single field of entry without having to specifically designate the field for one of these search types. In doing so this will provide greater flexibility over the results produced in a single search which is my goal in this suggestion.

i) I will define 3 operations: | (OR), & (AND) and ! (NOT). By using these symbols I reduce the amount of characters the user needs to type.

ii) I will consider terms separated by spaces without any special character in between to be implicit (OR) operations. This is concurrent with the default "oneword" behaviour of AjaxSearch and the bulk of popular search engines in use as of this writing, where search results by default are usually provided based on a partial, rather than complete, match of terms.

iii) Terms separated by (&) require both terms to be searched (same as "allwords" behaviour). Terms separated by (|) or by only space characters require at a minimum one of the terms (same as "oneword" behaviour). Terms prefixed by (!) will exclude any matches containing the term after the (!), i.e: it will return results that don’t contain the term (same as "notwords" behaviour). For logic evaluation purposes, (!) will also change a (&) operation to an (|) operation, an (|) operation to an (&) operation, and negate/cancel an existing (!) operation. This latter issue about logic evaluation will come into play during the ’bracketing’ definition later.

(&) and (|) always join terms. (!) prefixes term. (&) is always evaluated before (|). Brackets can be used to provide pairings of terms, thereby allowing a greater degree of control over the results:


---


Example with OR (equivalent statements in the same code block):



Returns results containing at least one of ’bob’, ’cat’ and ’dog’. These are all equivalent. Cleanup would need to be taken into account for malformed statements. For example:



For parsing purposes What should be done in a situation like this? Assume it is the start of a term. Where a (_) will represent any number of space characters, the following could all be considered equivalent for parsing purposes:



Meanwhile, any string that starts with:



or ends with:



should just have the information prior to term1 / after termX discarded.


---


Examples with AND (equivalent statements in the same code block):



1) Returns results that MUST contain ’bob’ and ’cat’
2) Returns results that contain ’dog’.



1) Returns results that MUST contain ’cat’ and ’dog’
2) Returns results that contain ’bob’.


Functional equivalents for malformed statements: identical behavior to the OR situation. See above and simply replace the (|) with a (&) in the explanation.


---


Example with NOT (equivalent statements in the same code block):




In this example:

1) Returns articles that do not contain the term ’monkey’
2) Returns articles that contain the term ’banana’
3) Returns articles that contain the term ’dog’ but that must also not contain the term ’cat’.


A second example (equivalent statements in the same code block):



1) Returns articles that do not contain the term ’monkey’
2) Returns articles that contain the terms ’banana’ and ’dog’, but that must also not contain the term ’cat’.

Functional equivalents for malformed statements:



This is valid, the spaces should just be ignored and term1 considered processed.

For trailing NOT operations such as:



Any information after termX should just be discarded as (!) only applies as a prefix to terms. It never joins terms; if it is found between terms, then it applies to the 2nd term only.


---


Example of malformed terminology:

If someone specifies a bunch of terms like this:



Aside from banning their IP for life, it would probably just be easiest to return a message saying malformed expression detected. The moment you have (&&), (||), (&|), (|&) or any number of spaces between them, just stop the parser and return a message to the results via a chunk or template file explaining the problem.

However, please be advised that this is valid:



A (!) is simply a negation. Negating a negation is a completely valid logic operation. Therefore "!!term2" is the same as writing ’term2’. In the above example there are eleven (!) symbols, therefore it is the same as "!term2", and therefore all results returned should not contain ’term2’.

---

Brackets to create strings of text:

For strings of text, say I want to search for the term ’disco fever’, simply enclose it in quotation marks:



Now ’disco fever’ and ’ I put a space before my search term’ are two separate search terms.

It would allow the site implementer some added control over how their site content search results are presented.
Of course, the term should be subject to being of minChars length, otherwise it should be removed. Additionally, you may wish to consider some form of validating terms. A term containing nothing but space characters between brackets Due to the international nature of MODx, the character used to surround strings should be one naturally available to the bulk of localizations. This character could be configurable. Alternatively you could use matching brackets instead if you prefer, such as ([) and (]) or ({) and (}), whatever is most convenient, accessible, but also user-friendly.


Additional note on brackets for search terms:

The only drawback is that as far as minChars is concerned, the system could be abused. For example, "e a" or " " would be valid search terms if minChars was equal to 3. This would start returning results that contained phrases like "They were also at the art store." which may constitute abuse of the system. It may be worth adding an option in that case to allow the site implementer to disable partial-match return for singular terms, "in quotes" terms, or both.


---


Brackets to contain and separate terms and operations:

Essentially, this will allow AjaxSearch to perform even more advanced logic operations where the order of operation priority (AND > OR > NOT) can be further governed by the use of brackets. I’ll go straight to the complex example and included bracketed search terms for good measure:



The above are equivalent statements. How would this complex string parse? Expanding the statement fully produces the following equivalent:



Suddenly it is much easier to interpret based on the order of operations:

1) Will return any results that must not contain ’27 marbles’ but must contain ’disco fever’.
2) Will return any results that must not contain ’27 marbles’ but must contain ’rabbits’.
3) Will return any results containing ’musical’.
4) Will return any results that must contain ’camera’ but must not contain ’tactical nuclear’.
5) Will return any results that must contain ’camera’ but must not contain ’strike’.

Finally, what if I enclosed the entire thing in brackets and prefixed it with a (!)?



Now it reduces to the following:



Without expanding the expression further, one can see that this will return all the articles NOT returned by the previous example.


---


Special character parsing:

To allow the parsing of special characters (&), (|), (!), (() and ()) as searchable text, require that they be contained within a closed string ". i.e.: anything between the first (") and the second, closing (") is considered text and not parsed for special symbols. Alternatively, one could use an escape code so that it is interpreted as text by the parser, but this is probably less user-friendly for the searcher. An escape may have to be used if you wanted to search for (") inside a term delineated by (") symbols. Depending on your chosen algorithm, the character or sequence for your escape code may also need an escape code, this is up to the developer’s progamming style.


---


Side notes ~ general thoughts on algorithms:

I come from a hardware background where NAND (negated AND) operations are wonderful and speedy. That being said, reducing boolean expressions in software and reducing them in hardware are two different beasts to tackle. Fully expanding an expression while great for illustrative purposes is probably not how you would want to tackle this in a program, so an optimization algorithm would be almost mandatory to continue to retain the speediness it is known for. If I fully expand that last example I gave, look what happens (search terms replaced with letters to save space):



That’s probably not going to be an especially fast evaluation, although it is an entirely valid boolean expression. In general reducing the number of terms as much as possible is ideal (note how that first expression contains fewer terms, and it can be reduced even further since that expression above is already an expanded version of an earlier example).

Here are some logic points worth keeping in mind: whenever a term is (AND)-joined to the negation of itself, this is the equivalent of returning nothing. Example:



This says return all documents that contain ’term1’ but that do not contain ’term1’; it is impossible to meet this condition, so without performing any search at all you know right away that the result is "no documents found". If anything else is (AND)-joined to that expression, you know it still evaluates to ’return nothing’.



The "term1 & !term1" reduces to nothing, anything (AND)-joined with nothing is nothing.

Conversely, if a term is (OR)-joined to the negation of itself, this is the equivalent of returning everything, so:



This says return all documents that contain ’term’ or that do not contain ’term1’; you know right this includes every article there is, so right away you can return all articles. If anything else is (OR)-joined to that expression, you know it still evaluates to ’return everything’.



The "term1 | !term1" reduces to everything, anything (OR)-joined with everything is everything.

On the other hand, (OR)-joining a "return nothing" expression to "something else" will return "something else". Similarly, (AND)-joning a "return everything" expression to "something else" will return "something else".



Both of the above evaluate to ’term2’.


---


I hope you have found this interesting as far as providing an additional and powerful search mode in AjaxSearch, thanks again for taking the time to look this over.


L

Rather than stuffing all of this into AjaxSearch, why not just create an AdvancedBooleanSearch add-on that implements this feature set?

@lacrossia

Thank you very much for this interesting post. Well documented and relevant.

Today the management of the advSearch is, IMHO, may be "simple" but effective.
I am not convinced by the necessity to offer a more complicated search like "boolean search".

Today when somebody do a search in content & tvs, with 5 differents search terms we get a mySql which looks like (with &advSearch=`allwords`) this one :Which is already a complicated request. So Due to the number of fields to take into account, I am not convinced by the feasability to develop a "boolean" search which will increase again the complexity of the SELECT request.

When I have decided to implement the advanced search, I take example on Google search with its advanced search http://www.google.co.uk/advanced_search?hl=en
I think that it is a good compromise between complexity of algotithm (and support) and simplicity for the end user.

And to be honest, I haven’t enough time to implement this kind of feature which will need lot of testing and support.