When I begun with the goal of looking for a better way to compress a string in real time in memory while gaining fast query capabilities, I had a Rust Generalized Suffix Tree built naively on top of a C Library called LibART (Adaptive Radix Tree). It gave me super fast prefix, suffix and contains like no other would believe. At the expensive of memory.

For example, a pathological case of 300k 128 Alphanumeric strings would take 6GB. If you do the calculation based on unicode, you'll see it doesn't take much ...

Update: Found several bugs in my Typescript and Rust implementation that looks to invalidate the results here. Either I stumbled into a way to construct a minimized graph that can find what I want or what. Only found it after I implemented a traverser with backwards lookup. Might as well use a Finite State Transducer Index as far as I can see. I'm going to keep looking into this since it is a radix and suffix tree.

- One of the bugs is related to my misreading of the paper. One should not use same terminator...

Part 2: https://www.normansoven.com/post/obessed-with-making-a-generalized-suffix-indextree-memory-efficient-part-2

I am so obessed that I threw away the Suffix Index and pursued its successor, the DAWG. Well, the compact version anyway: CDAWG!

Note: DAWG is a Directed Acyclic Word Graph also called a Minimal Acyclic Finite State Automaton (MAFSA) or Minimal Acyclic Deterministic Finite Automaton (MADFA). CDAWG means Compact Directed Acyclic Word Graph.

Story

Oh man, I cannot believe my eyes when I saw the resu...

Part 1: https://www.normansoven.com/post/obessed-with-making-a-generalized-suffix-indextree-memory-efficient

Part 3: https://www.normansoven.com/post/obessed-with-making-a-generalized-suffix-indextree-memory-efficient-part-3

Merged Trie Experiment

I read parts of an interesting paper called MergedTrie Efficient textual indexing. Paper and code is here: https://github.com/AntonioFerrandez/MergedTrie

I wanted to figure out if there was a way to decrease the amount of memory (approximately in half) for a Suffix In...

Part 2: https://www.normansoven.com/post/obessed-with-making-a-generalized-suffix-indextree-memory-efficient-part-2

I created a Generalized Suffix Index based on a Radix Trie (libART, Adaptive Radix Trie) around the beginning of 2019. The one thing I noticed about it was that is will take YUGE amounts of memory because of how many containers are allocated. I used a Rust HashSet with SeaHash after some testing at that time because it was good enough to me. The index stores strings => int64 and SeaHash is good...

or the fewest places possible. Cache invalidation is hard, so why make your problems harder by multiplying it?

I've been thinking about a comment made here about "cacheless architecture": https://www.reddit.com/r/java/comments/dbtog0/where_is_my_cache_architectural_patterns_for/f2am2vn/

We went from a tangled caching mess architecture to a completely cacheless architecture at a higher volume than we could manage before. Clients request data once and keep it up to date with patch streams. Queries are effici...

Couple of months ago I wanted to talk about the Configuration Triad: Configuration Provisioning, Distribution and Provider.

If have not seen my Open Source Config Provider, C5Store, well you can find it on github.

Going to talk about the triad in reverse in kind of the way an application developer works with configuration.

Provider

Provider is the interface to a configuration

Hard coding is the simplest form, the values are provided in code.

Typically a developer uses a file, reads from the file, deserializes it...

Link: https://github.com/ingydotnet/git-subrepo

I was thinking about how to distribute configuration (including secrets) in my applications recently so naturally the idea of using git as a way to facilitate the distribution of configuration data pops up. How can I store the configuration in a way that is part of the project repository, but separate so that configuration can be checked out, changed, committed and pushed out as if it were part of the project repository?

Git SubModule, of course. Only problem wi...

Disclaimer: This is more proof of concept than anything else.

I was setting up Sonatype's Nexus yesterday and was very annoyed at the setup ceremony associated with it. I got it working with SystemD's dynamic user, but the way it needs to be setup is insane to me. Why is it so expensive to set up?

I set the DataDir to /var/lib/private/...etc... the state directory for a Dynamic User. Karaf has some java -D options, I tried to move the config and Nexus would not start. I'd get errors like status=254/n/a or 255...

I wonder who thought the way that `npm link` should work figured that no one would ever try to use local modules on their computer. I'm really incensed by the idea that modules that are the same version across multiple local dependencies are considered separate.

Consider

App A -> Lib A -> Lib B

           -> Lib B

One would reasonably believe that if all of these modules are linked together via npm or yarn link that there would be one instance of each module. No.

App A has its own instance of Lib B, so if you we...