trigram_grep: A C++ repository from turing228

Trigram Grep Finder

Trigram Grep Finder is the application of the future that allows you to find fastly a string in files and manually check all found matches!

Instruction of use
Quickstart
Used tecnhologies
Idea of the solution
Files description
Benchmarks
Personal impression
Contributors
License

📖 Instruction of use

First screen is this. Click on the folder's icon in the upper left conner and select a directory!

Now click "choose". The application will start indexing. In the future you will find strings in files of this directory

You can see the progress bars and timings at the bottom of the application.

If you want, you can stop the indexing for a while and start searching. Just click on the button "stop".

After the indexing is over or you've clicked "stop" you can search strings. Use the special input field in the upper part of the application

If you've typed the search string, on the left side you see all files with it. Choose one and click on it! On the right side - the content of the chosen file. Amazing!

You can see at the upper right side of the application number of matches with the search string, the number of the currently selected match and navigation on matches buttons. Use the last to get the best experience!

Also you can open the file or the path where it is just by special buttons at the bottom of the application!

🚀 Quickstart

You have two options:

CMake-way building:

$ cmake -DCMAKE_BUILD_TYPE=Debug .
$ make

You are also free to write if you want, for example, -DCMAKE_BUILD_TYPE=RelWithDebInfo instead of -DCMAKE_BUILD_TYPE=Debug

QMake-way building:

$ qmake CONFIG+=debug -o Makefile extra_files_finder.pro
$ make

To run it just write in your terminal:

$ ./trigram_grep

📋 Used technologies

QT framework - for UI and multithreading
C++ - as the language for the backend development
Mutexes - for the multithreading correctness

🎉 Idea of the solution

Ok, that is very easy to describe:

Firstly, we index the selected directory by the method "trigram grep" (described by Google's developers). That means we remember in QSet<quint32> file_trigrams all trigrams inside each file (trigram is a sequence of exactly 3 letters) (yes, we represent trigrams as quint32, for more details check the code)
Secondly, to fastly find the search string, we memorize trigrams of the search string
Finally, we fastly check every file does it contain the search trigrams and then manually check does it contain the whole search string

📂 Files description

Code of the application:

main.cpp - file with function main
mainwindow.h, mainwindow.cpp - the code of the main application
IndexingWorker.cpp, IndexingWorker.h - for the first step in our idea. Starts in a new QT-thread
SearchingWorker.cpp, SearchingWorker.h - for the third step. It starts in an extra thread by mainwindow.cpp. Starts in a new QT-thread
Trigram.cpp, Trigram.h - helper class for working with file lists (e.g. to remember what trigrams are there)

Also:

mainwindow.ui — XML-file with the description of the main window. Utility uic uses it for the building of the file ui-mainwindow.h, which includes to mainwindow.cpp. ui-files can be opened by QT Designer or QT Creator.
CMakeLists.txt — cmake's build-script.
trigram_grep.pro — qmake's build-script.

🏄 Benchmarks

Indexing by trigrams is as fast as reading from a hard drive, so it depends on what you have - HDD or SSD (100-500 MB/s). To solve the problem of finding string in files you must at least once read all data where your string can be, so it's the sensational result that our indexing function doesn't decrease at all the maximum possible speed!

On the other hand, the application finishes searching after 0.5-1s depending on the directory's size. It's almost the same speed as you type symbols in the search string field!

Amazing, is not it?

💣 Personal impression

QT is a very cool framework! It allowed to me easily create a beautiful and convenient UI with wide functionality & implemented multithreading. But "easily", because at some point, I finally figured out everything! This is an incredibly exciting experience of learning new technologies 📚, googling 🔍, overcoming 🧗 the framework's limitations, testing 🌶️ and immediately viewing 👀 the result 💥🔥🎆 !!!

Thanks a lot to sunny white Saint Petersburg nights 🌙, deadlines ☠️, Google 🤝 and friends 💞. You are breathtaking 💋 !!! You all helped me a lot to develop this amazing application!!!!