aho-corasick
fzf
aho-corasick | fzf | |
---|---|---|
21 | 407 | |
950 | 59,920 | |
- | - | |
7.2 | 9.6 | |
about 1 month ago | about 18 hours ago | |
Rust | Go | |
The Unlicense | MIT License |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
aho-corasick
- Aho-Corasick Algorithm
-
Identifying Rust's collect:<Vec<_>>() memory leak footgun
You can't build the contiguous variant directly from a sequence of patterns. You need some kind of intermediate data structure to incrementally build a trie in memory. The contiguous NFA needs to know the complete picture of each state in order to compress it into memory. It makes decisions like, "if the number of transitions of this state is less than N, then use this representation" or "use the most significant N bits of the state pointer to indicate its representation." It is difficult to do this in an online fashion, and likely impossible to do without some sort of compromise. For example, you don't know how many transitions each state has until you've completed construction of the trie. But how do you build the trie if the state representation needs to know the number of transitions?
Note that the conversion from a non-contiguous NFA to a contiguous NFA is, relatively speaking, pretty cheap. The only real reason to not use a contiguous NFA is that it can't represent as many patterns as a non-contiguous NFA. (Because of the compression tricks it uses.)
The interesting bits start here: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...
-
Ask HN: What's the fastest programming language with a large standard library?
Right. I pointed it out because it isn't just about having portable SIMD that makes SIMD optimizations possible. Therefore, the lack of one in Rust doesn't have much explanatory power for why Rust's standard library doesn't contain SIMD. (It does have some.) It's good enough for things like memchr (well, kinda, NEON doesn't have `movemask`[1,2]), but not for things like Teddy that do multi-substring search. When you do want to write SIMD across platforms, it's not too hard to define your own bespoke portable API[3].
I'm basically just pointing out that a portable API is somewhat oversold, because it's not uncommon to need to abandon it, especially for string related ops that make creative use of ISA extensions. And additionally, that Rust unfortunately has other reasons for why std doesn't make as much use of SIMD as it probably should (the core/alloc/std split).
[1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...
[2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...
[3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...
-
Ripgrep is faster than {grep, ag, Git grep, ucg, pt, sift}
Oh I see. Yes, that's what is commonly used in academic publications. But I've yet to see it used in the wild.
I mentioned exactly that paper (I believe) in my write-up on Teddy: https://github.com/BurntSushi/aho-corasick/tree/master/src/p...
-
how to get the index of substring in source string, support unicode in rust.
The byte offset (or equivalently in this case, the UTF-8 code unit offset) is almost certainly what you want. See: https://github.com/BurntSushi/aho-corasick/issues/72
-
Aho Corasick Algorithm For Efficient String Matching (Python & Golang Code Examples)
This is an implementation of the algorithm in Rust as well if someone is curious. Though this code is written for production and not teaching.
-
When counting lines in Ruby randomly failed our deployments
A similar fix for the aho-corasick Rust crate was made in response
-
Aho-corasick (and the regex crate) now uses SIMD on aarch64
Teddy is a SIMD accelerated multiple substring matching algorithm. There's a nice description of Teddy here: https://github.com/BurntSushi/aho-corasick/tree/f9d633f970bb...
It's used in the aho-corasick and regex crates. It now supports SIMD acceleration on aarch64 (including Apple's M1 and M2). There are some nice benchmarks included in the PR demonstrating 2-10x speedups for some searches!
- Stringzilla: Fastest string sort, search, split, and shuffle using SIMD
-
ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}
Even putting aside all of that, it might be really hard to add some of the improvements ripgrep has to their engine. The single substring search is probably the lowest hanging fruit, because you can probably isolate that code path pretty well. The multi-substring search is next, but the algorithm is very complicated and not formally described anywhere. The best description of it, Teddy, is probably my own. (I did not invent it.)
fzf
-
Ask HN: Any tool for managing large and variable command lines?
In addition, I think bash's `operate-and-get-next` can be very helpful. When you go back through your shell history, you can hit Ctrl+o instead of enter and it will execute the command then put the next one in your history on the command line, and keep track of where you are in your history. This way, you can rerun a bunch of commands by going to the first one and Ctrl+o till you are done. And you can edit those commands and hit Ctrl+o and still go to the next previously run command.
Note: fzf's history search feature breaks this. https://github.com/junegunn/fzf/issues/2399
-
pyfzf : Python Fuzzy Finder
fzf : https://github.com/junegunn/fzf
- Command Line Fuzzy Search
-
So You Think You Know Git – Git Tips and Tricks by Scott Chacon
Those are the most used aliases in my gitconfig.
"git fza" shows a list of modified/new files in an fzf window, and you can select each file with tab plus arrow keys. When you hit enter, those files are fed into "git add". Needs fzf: https://github.com/junegunn/fzf
"git gone" removes local branches that don't exist on the remote.
"git root" prints out the root of the repo. You can alias it to "cd $(git root)", and zip back to the repo root from a deep directory structure. This one is less useful now for me since I started using zoxide to jump around. https://github.com/ajeetdsouza/zoxide
-
Which command did you run 1731 days ago?
> my history is so noisy I had to find another way
The fzf search syntax can help, if you become familiar with it. It is also supported in atuin [2].
[1]: https://github.com/junegunn/fzf#search-syntax
[2]: https://docs.atuin.sh/configuration/config/#fuzzy-search-syn...
-
Z – Jump Around
You call it with `n` and get an interactive fuzzy search for your directories. If you do `n ` instead, it’ll start the find with `` already filled in (and if there’s only one match, jump to it directly). The `ls` is optional but I find that I like having the contents visible as soon as I change a directory.
I’m also including iCloud Drive but excluding the Library directory as that is too noisy. I have a separate `nl` function which searches just inside `~/Library` for when I need it, as well as other specialised `n` functions that search inside specific places that I need a lot.
¹ https://github.com/sharkdp/fd
² https://github.com/junegunn/fzf
-
alacritty-themes not working any more!!!
View on GitHub
-
Fish shell 3.7.0: last release branch before the full Rust rewrite
I do find the history pager stuff interesting, but ultimately not of tremendous use for me. I rebound all my history search stuff to use fzf[1] (via a fish plugin for such[2]), and so haven't been aware of the issues
[1] https://github.com/junegunn/fzf
[2] https://github.com/PatrickF1/fzf.fish
-
Ugrep – a more powerful, ultra fast, user-friendly, compatible grep
You can also use fzf with ripgrep to great effect:
[1]: https://github.com/junegunn/fzf/blob/master/ADVANCED.md#usin...
- Tell HN: My Favorite Tools
What are some alternatives?
uwu - fastest text uwuifier in the west
peco - Simplistic interactive filtering tool
ripgrep - ripgrep recursively searches directories for a regex pattern while respecting your gitignore
zsh-autocomplete - 🤖 Real-time type-ahead completion for Zsh. Asynchronous find-as-you-type autocompletion.
perf-book - The Rust Performance Book
z - z - jump around
bat - A cat(1) clone with wings.
zsh-autosuggestions - Fish-like autosuggestions for zsh
fd - A simple, fast and user-friendly alternative to 'find'
mcfly - Fly through your shell history. Great Scott!
StringZilla - Up to 10x faster strings for C, C++, Python, Rust, and Swift, leveraging SWAR and SIMD on Arm Neon and x86 AVX2 & AVX-512-capable chips to accelerate search, sort, edit distances, alignment scores, etc 🦖
ranger - A VIM-inspired filemanager for the console