Change EmojiTrie implementation to SuffixTree

Expensify / App

Welcome to New Expensify: a complete re-imagination of financial collaboration, centered around chat. Help us build the next generation of Expensify by sharing feedback and contributing to the code.

https://new.expensify.com

MIT License

3.59k stars 2.92k forks source link

Change EmojiTrie implementation to SuffixTree #51148

Open hannojg opened 1 month ago

hannojg commented 1 month ago

For this issue ticket we have implemented a very efficient/fast suffix tree implementation:

https://github.com/Expensify/App/issues/46591

PR:

https://github.com/Expensify/App/pull/48652

It was discussed that we want to use the implementation of the SuffixTree for the emoji search as well:

Discussion here

This enables:

more efficient search in emojis
faster construction of the emoji tree (we should compare the construction time before and after the change.)
searching for any substring of an emoji name (not just perfect name matches)

hannojg commented 1 month ago

cc @roryabraham

ChavdaSachin commented 1 month ago

Hey @hannojg, I have been very passionate Competitive Programmer back during my college days. I think I could be a help here. Do you think there is a scope for an External contributor here?

hannojg commented 1 month ago

I think this is more of an internal ticket. The suffix tree implementation has already been built by our internal team and this is a follow up issue from one of our PRs.

ChavdaSachin commented 1 month ago

Alright, But I have one more suggestion here, we could make use of c++ here instead of js , c++ is well known for it's speed, I am really positive that c++ would make significant improvement here.