Parsing Text search expression

[Mike Torrettinni 198]

I have a very simple text search feature that uses Pos() to locate search text in string.

Now I want to extend it to handle just a little more complex phrases. I think the most complex examples I need to implement includes:

- brackets

- quotes for full phrase

- and AND/OR

 

Probably most complex example: ("test phrase" OR testing) AND text OR "anything else"

I assume most common will be simple examples like:

test OR test2

test OR "test case"

test AND test2

 

I have all text in arrays with object IDs to know where it belongs, records like: CustomerID, Address, Name, Notes;  DocID, Title, Description, Notes...  - and all fields except CustomerID, DocID are searchable strings.

 

One idea is to try to convert search expression into regex, the other one if to parse the expression and try to make logical search as needed (this would probably be most complex to implement).

 

I see examples of using database and use their advanced search capabilities like: https://zarko-gajic.iz.hr/full-text-search-functionality-in-delphi-applications-implementation-idea/

But this is just one small feature of my full project, so I'm not really sure I want this to be reason to implement database, even the lightest ones.

 

I appreciate any suggestions on parsing such expression, converting to regex.. perhaps there are components that already do same or similar things.

 

 

 

 

 

[Guest]

I am not sure i do understand your quest completely, but will guess a little !

 

First, the records you listed look like a DB columns, so, is SQL approach is on the table ? 

By using SQL you do need nothing else, SQL in fact built to such search and much more complex syntaxes, but again i am guessing here, and to add to this, to my knowledge the most comprehensive SQL parser for pascal is the one by NexusDB, there is one file called nxSQLParse.pas and it is freaking scary !

Also there is many Pascal/Delphi scripters engine that do similar things, most of them are insightful, From the powerful TMS Scripter, to RTC, or Delphi HTML, ... the list is long and browsing the code is valuable knowledge.

 

But again, guessing you did not miss the SQL choice, so let me explain how i did many similar filtering on big data with complex syntaxes, although in my case it wasn't text at all.

I will try to explain with an example from your sample syntax, and hoping you will get the idea.

 

Your syntax is ("test phrase" OR testing) AND text OR "anything else"

First lets dissect syntax into pieces, we will solve this by the most simple and least complex way, divide and conquer !

1) Separate by the logic operators, means we will be left with a list of searchable text 

"test phrase"

testing

text

"anything else"

2) Build logic flow accordingly to brackets, here a little knowledge in how mathematical expression being parsed will be a great help, see we brackets and logic operators are similar to brackets, +, -, *,/ , after building the flow which almost modified version of the list in (1) with which one comes first then applied to which, there is many Pascal/Delphi mathematical expression parsing code out there.

3) Search for each item in (1) and build a new list (an array) for it, yes this seem expensive, but let it be for now.

4) Apply the Flow you built in (2) on the lists generated from (3), with each step you will be building a new list, this might be easier from adding or removing from/into (aka changing) a list, the last list is the search result.

 

Simple, Right ? 🙂

 

Later, and after making this work, you can go after eliminating unneeded lists, like the case with ("test phrase" OR testing), these can be handled as one list, but again make it work first in the simplest way you can, only after that you can refactor and redesign it with more complex but faster and less memory usage.

 

May be others will suggest different approaches, but now this what i can thing of, which i see can fit your need, and it will be elegant.

[Mike Torrettinni 198]

Thank you @Kas Ob., yes SQL is not on the table.. unless all other options are too complex to implement, but I doubt it.

 

I was thinking similar thing as you to parse expression and build some logical expression out of it and then run on text. But my idea was (just an idea so far) to run a full logical expression on each string, while your suggestion is to create lists based on parts of expression and then combine/cross-sect lists as operators say, right?

So, my idea was to parse expression to end up with something like:

 

this is as stage 3) in your example

function EvalPhraseInText(const aText: string): boolean;
begin
  Result := 
    ((Pos('text_phrase', aText)>0) OR (Pos('testing', aText) > 0 ))// replace 
    AND Pos('text', aString) > 0
    OR (Pos('anything else', aString)> 0;
end;

of course, I have no idea how to get to this point, at the moment, as this would be point 2) build logic flow.

 

I assume you thought of this approach when you were working on your solution and decided that is not as good as your solution.

 

 

 

 

 

[Alexander Sviridenkov 356]

27 minutes ago, Kas Ob. said:

the most comprehensive SQL parser for pascal is the one by NexusDB, there is one file called nxSQLParse.pas and it is freaking scary !

HTML Library Bundle contains SQL framework with SQL parser for Firebird, Oracle, MySQL, Postgres, Microsof SQL, Elevate and SQLite. Library supports query parsing, formatting, translation between SQL dialects, modifying (change order, where, limit, fields, etc) syntax check and DB schema check, editor completion implementation and much more. https://delphihtmlcomponents.com/SQLLibrary.pdf

[Guest]

41 minutes ago, Mike Torrettinni said:

But my idea was (just an idea so far) to run a full logical expression on each string, while your suggestion is to create lists based on parts of expression and then combine/cross-sect lists as operators say, right?

 

45 minutes ago, Mike Torrettinni said:

I assume you thought of this approach when you were working on your solution and decided that is not as good as your solution.

Well, in my many written filters and search expression were mostly math expression to isolate ranges, means i was for some criteria's with defined values while including/excluding ranges (>,<, <= ...) so lists was essential here as they some search statements explicitly required medians ( also deviations...) like values from ranges, so building lists was the fastest approach.

 

Also there is cache usage which in some cases i had to choose this based on my benchmarks, anyway i don't think extreme speed is essential in your case because you need result and that what you care about, were in my case i want to repeat this many times and render many details visually, so 50ms is my upper tolerated limit, when i have millions of records.

 

59 minutes ago, Mike Torrettinni said:

this is as stage 3) in your example

No !, far from that, this is what you is the only approach, 

  function Search(const Text:string; const List:TSomeList):TSomeList;
  ...


  TLogicOperation = (loAND, loOR, loXOR);

  TFilter = class
  protected
    //FLogicOperation: TLogicOperation;
    function ApplyFilter(const List1, List2: TSomeList): TSomeList; virtual; abstract;
  public
    //constructor Create(Operation: TLogicOperation = loAND);
    function Apply(const List1, List2: TSomeList): TSomeList;
    //property FilterOperation: TLogicOperation read FLogicOperation write FLogicOperation;
  end;

  TFilterOR = class(TFilter)
  protected
    function ApplyFilter(const List1, List2:TSomeList): TSomeList; override;
  end;

That is a messy salad of two or three approaches, also a helper will do !

ApplyFilter will do one thing, the real code can be very short and accurate, consider it as food for thoughts.

And there should be a list of the filters and their sequence built by your parser, just don't over think it, in the imaginary code you will feed the result from ApplyFilter to another ApplyFilter as parameter.

 

Anyway ,

48 minutes ago, Mike Torrettinni said:

of course, I have no idea how to get to this point, at the moment, as this would be point 2) build logic flow.

Well, you know how to do it and it will be clear if you give it some time, just think outside the box, and relax your assumptions, again there is many approaches to handle it your way, but the questions is how to build chain of action at runtime, you know how to it, right?

only the flow i mentioned it will be simple as TAnd and TOr where these are any creatures you like, record, class or even raw list of actions built with your parser, may be each action will have pointer to the next action, not much explained in this way, but try to think about it and all the pieces will fall in place, (trust me it is easy)

 

I can't remember if it was you or not, who asked about JIT in this forum, see when you finished resolving this, you already built a JIT !, this is off-topic but extreme JIT will replace these line of logic with may be assembly optimized code and run them.

[Guest]

1 hour ago, Alexander Sviridenkov said:

HTML Library Bundle contains SQL framework with SQL parser

Well, i don't have the Bundle License, it is nice to know.

 

Also i want to point to the fact that the page for "HTML Report Library" is mentioning script engine and "designed to generate reports using databases and XML"

Quote

Build-in powerful scripting and expression evaluation engine allow to implement complex data processing algorithms and encapsulate all logic inside report.

But doesn't mention SQL explicitly.

[Mike Torrettinni 198]

1 hour ago, Kas Ob. said:

Also there is cache usage which in some cases i had to choose this based on my benchmarks, anyway i don't think extreme speed is essential in your case because you need result and that what you care about, were in my case i want to repeat this many times and render many details visually, so 50ms is my upper tolerated limit, when i have millions of records.

It's triggered on user input, so no need for super fast. I do have 'instant search' (search as you type), but this is not applicable for complex cases or if you type really fast,

I guess under 1s should be just fine. 

 

Oh, I do have highlighting of text for visual representation, but that only works on a found results, so doesn't need to be super fast, either.

 

Thanks, you gave me a lot to think about!

Edited July 26, 2021 by Mike Torrettinni

[Bob Devine 11]

+1 for HTML Library

[Mike Torrettinni 198]

4 hours ago, Bob Devine said:

+1 for HTML Library

Yes, it's very powerful component, shame it can't parse expressions that are not pure SQL. I could probably customize my expression to add 'SELECT' and other sql keywords to parse, but that is not what I'm after.

 

[Alexander Sviridenkov 356]

15 minutes ago, Mike Torrettinni said:

Yes, it's very powerful component, shame it can't parse expressions that are not pure SQL. I could probably customize my expression to add 'SELECT' and other sql keywords to parse, but that is not what I'm after.

 

 

It can. Just override GetDialect method (uses sqlparse)

 

type
  TCustomExpression = class(TSQLExpression)
  private
    FDialect: TSQLDialect;
  public
    function GetDialect: TSQLDialect; override;
    destructor Destroy; override;
  end;

destructor TCustomExpression.Destroy;
begin
  FDialect.Free;
  inherited;
end;

function TCustomExpression.GetDialect: TSQLDialect;
begin
  if  FDialect = nil then
    FDialect := TSQLDialect.Create;
  Result := FDialect;
end;

procedure TForm67.Button1Click(Sender: TObject);
var SE: TCustomExpression;
begin
  SE := TCustomExpression.Create(nil);
  SE.ParseString('user=''john'' or user = ''peter''');
  ShowMessage(SE.Node.Children[0].Children[1].Name); //=john
end;

 

Also there is pascal expression class in htscriptparse unit:

 

var SE: TScriptExpression;
begin
  SE := TScriptExpression.CreateAndParse('(user=''john'') or (user = ''peter'')');
  SE.Variables['user'] := 'peter';
  ShowMessage(SE.Calc)

 

[Fr0sT.Brutal 900]

There are plenty of open-source parsers available.

- ZeosDBO has powerful engine in \src\core\ (units ZExpression.pas, ZExprParser.pas, ZExprToken.pas, ZTokenizer.pas), you could take any part of it and customize to your needs

- IBExpress from std lib has RAD\source\IBX\IBX.IBScript.pas with the parser as well, just as FireDAC in RAD\source\data\firedac\FireDAC.Stan.Expr.pas for expressions and FireDAC.Comp.Script.pas for scripts

- Template engine from DVDChief also has expression parser

- and so on

Moreover, with such simple tokens you can easily write it yourself

 

Btw, I don't realize what "testing" and "text" are in your example. Variables? Or just single words to search for, with quotes removed for simplicity (a la Google)?

That's a nice task to solve, huh. Depending on maximum nesting level allowed it could require some discrete maths.

Edited July 27, 2021 by Fr0sT.Brutal

[Mike Torrettinni 198]

1 hour ago, Fr0sT.Brutal said:

what "testing" and "text" are in your example

 

User input search string, yes like google. I mean simple edit box.

No nested levels at this point.

 

Thanks for suggestions!

[Fr0sT.Brutal 900]

13 hours ago, Mike Torrettinni said:

User input search string, yes like google. I mean simple edit box.

Then SQL parsers won't help you much or you'll have to manually mix what they consider variables and string literals into one category.

[Mike Torrettinni 198]

3 hours ago, Fr0sT.Brutal said:

Then SQL parsers won't help you much or you'll have to manually mix what they consider variables and string literals into one category.

Yes, I think you are right. Probably I can make it work with a lot of modification to fit within case like this:

 

19 hours ago, Alexander Sviridenkov said:

SE.ParseString('user=''john'' or user = ''peter''');

I think this would require quite a modification of expression from: 'john or peter' to 'user = john or user = peter'.

I assume to actually replace Pos(), would need to use LIKE (or CHARINDEX)

SE.ParseString('user LIKE ''%john%'' or user LIKE ''%peter%''');

 

[Fr0sT.Brutal 900]

2 hours ago, Mike Torrettinni said:

I think this would require quite a modification of expression from: 'john or peter' to 'user = john or user = peter'.

Just don't forget to foresee cases when someone would wish to search for "or" (as a word) 🙂

Minimalistic free-form searches are cool (imagine if Google required us to write "word='foo' or word='bar" instead of "foo bar") but slightly more complex to implement with all edge cases. That's why Google uses specific symbols for logical operations

[Mike Torrettinni 198]

16 minutes ago, Fr0sT.Brutal said:

Just don't forget to foresee cases when someone would wish to search for "or" (as a word) 🙂

Minimalistic free-form searches are cool (imagine if Google required us to write "word='foo' or word='bar" instead of "foo bar") but slightly more complex to implement with all edge cases. That's why Google uses specific symbols for logical operations

I think I could instruct to use double-quotes for or/and and other operators, like it's used for phrases: "or customer" or "and customer" or "or" or "and" ....

[FabDev 8]

On 7/27/2021 at 12:52 PM, Bob Devine said:

+1 for HTML Library

I confirm that HTMLLibrary is an awesome HTML library. Congratulation Alexander 😉

 

But for the SQL parser of HTML library I don't find how to transform this :

Peter or "Bibi Paulo" and John

 

to a where clause to search on a field :
 

select xxx where
Name containing 'Peter' or Name containing 'Bibi Paulo' and Name containing 'John'

 

Edited July 29, 2021 by FabDev

[darnocian 84]

I felt like playing with this idea for Delphi - as like writing parsers. 😉 Years ago I did something similar for a document management system in a different language. I've written a small demo illustrating 2 ways of parsing https://github.com/sempare/sempare-delphi-fts-expression

 

I did this for fun and in a few hours, so it is still very raw. It contains a hand rolled lexer and parser, but hopefully can give you some ideas how to do this too.

 

In the first (Sempare.FullTextSearch.SimpleExpression.Test.pas) you can see some scenarios:

procedure TSimpleExprTest.TestSimpleExpr;
begin
  assert.AreEqual('name = ''conrad''', tparser.ParseStr('name', '"conrad"'));
end;

procedure TSimpleExprTest.TestWildCard2Expr;
begin
  assert.AreEqual('(name like ''conrad%'') or (name like ''%pete'')', tparser.ParseStr('name', '"conrad%" "%pete"'));
end;

procedure TSimpleExprTest.TestWildCardExpr;
begin
  assert.AreEqual('name like ''conrad%''', tparser.ParseStr('name', '"conrad%"'));

end;

procedure TSimpleExprTest.TestNotExpr;
begin
  assert.AreEqual('not (name = ''conrad'')', tparser.ParseStr('name', 'not "conrad"'));
end;

procedure TSimpleExprTest.TestOrExpr;
begin
  assert.AreEqual('(name = ''abc'') or (name = ''def'')', tparser.ParseStr('name', '"abc" or "def"'));
end;

procedure TSimpleExprTest.TestPrecidentExpr;
begin
  assert.AreEqual('(name = ''abc'') and (not ((name = ''321'') or (name = ''def'')))', tparser.ParseStr('name', '''abc'' and  not ''321'' or  ''def'''));
end;

 

The second (Sempare.FullTextSearch.Expression.Test.pas) is a bit more general. It illustrates parsing, but implementation at present is fairly basic as just a pretty printer:

procedure TExprTest.TestNotExpr;
begin
  assert.Areequal('not (name != ''conrad'')', tparser.ParseStr('not (name!="conrad")'));
end;

procedure TExprTest.TestOrExpr;
begin
  assert.Areequal('(name = ''abc'') or (text = ''def'')', tparser.ParseStr('name = ''abc'' or text = ''def'''));
end;

procedure TExprTest.TestPrecidentExpr;
begin
  assert.Areequal('((name = ''abc'') and (value = ''321'')) or (text = ''def'')', //
    tparser.ParseStr('name = ''abc'' and value = ''321'' or text = ''def'''));
end;

procedure TExprTest.TestStartsWithExpr;
begin
  assert.Areequal('name like ''abc%''', tparser.ParseStr('name starts with "abc"'));
end;

above you can see that the parsing identifies the precedence and places brackets appropriately. Also it changed 'starts with' to 'like'...

 

NOTE: there are 2 different parsers implemented for the above scenarios (but both named TParser - just depends which unit is being referenced)

 

Hope you find this useful.

Edited July 30, 2021 by darnocian

[generic 0]

I really suggest to use a library that does the work for you.

To name at least one: Lucene 

 

If you want to use some server software, use elastic search or the build in fulltext catalogs in sql databases.

 

[Mike Torrettinni 198]

7 minutes ago, generic said:

I really suggest to use a library that does the work for you.

Why would you suggest that?

 

10 minutes ago, generic said:

Lucene 

 

I would prefer Delphi solution, do you know of Lucene in Delphi?

[mvanrijnen 123]

Maybe create a wrapper around: Welcome to the Lucene.NET website! | Apache Lucene.NET 4.8.0 ? 

Will be a lot of work i think.

 

[Mike Torrettinni 198]

1 minute ago, mvanrijnen said:

Maybe create a wrapper around: Welcome to the Lucene.NET website! | Apache Lucene.NET 4.8.0 ? 

Will be a lot of work i think.

 

Thanks, if this was a major feature I need, I might take on the project.

[mvanrijnen 123]

Would be nice to have a common parser what you posted in your startpost, something with a base class which does the basic parsing of the query, and which can be extended in execution functionality .

[Mike Torrettinni 198]

14 minutes ago, mvanrijnen said:

Would be nice to have a common parser what you posted in your startpost, something with a base class which does the basic parsing of the query, and which can be extended in execution functionality .

Will post when I make progress.

[darnocian 84]

Lucene is really excellent! I can highly recommend it! I've only used it in Java. I've considered doing a port, but it is a big project to undertake.

 

BTW. There is an older port on sourceforge: https://sourceforge.net/projects/mutis/