String pattern matching algorithm learning

General discussion related to "Everything".
Post Reply
Meepo
Posts: 2
Joined: Thu Jul 29, 2021 6:53 am

String pattern matching algorithm learning

Post by Meepo » Thu Jul 29, 2021 7:06 am

Hello, I am a student who is implementing a simple version of everything,
everything searches files super fast, so I want to implement a simple version myself in c++
I've already got all the files saved in vector by USN and MFT
But I'm having a big performance problem with string pattern matching
My search string has to match every file name in the vector, I've tried kmp, LCS, but these can't reach the second response time, I'd like to ask you for any suggestions

The only solution I have here to reach milliseconds is
if(it->filename == searchStr)
But I want to do some fuzzy search, like
searchStr = abc
filename = aaa823bbb34c
This would also match
Thank you very much for your help!

void
Site Admin
Posts: 7532
Joined: Fri Oct 16, 2009 11:31 pm

Re: String pattern matching algorithm learning

Post by void » Fri Jul 30, 2021 7:17 am

Everything uses a custom strstr search for pattern matching.

Multiple threads might help with performance.


I had trouble getting a Levenshtein distance search to return acceptable results.
With a short distance, cat would match bat.
With a longer distance, sonic would match tonic.
Some filenames do not use words from a dictionary, eg: Notepad.exe

Results would be OK if sorted by a rank.
Levenshtein distance performance was OK.

Meepo
Posts: 2
Joined: Thu Jul 29, 2021 6:53 am

Re: String pattern matching algorithm learning

Post by Meepo » Fri Jul 30, 2021 9:09 am

Thank your very much for your reply
I found the sdk on your website,
and i try it
then...
Due to my lack of multithreading knowledge
My interface stucks in every moment i type a character....,and always crash..

Thank you again for your help, I will learn some multithread,,OS,,and so on...

Post Reply