# Using a radix tree to find case-insensitive matches in large files

I'm using a radix tree library to find case-insensitive matches from several relatively large files (~24 files each on the order ~150MB).

My current algorithm requires me to read the chars of an entire file zipped with their index because finding the offset of match in the file is a requirement.

Currently the processing is quite slow because I am doing redundant work on each new character. However, the alternative is to create subtries, which is memory intensive.

My (not well-commented) code is below... If anything is unclear, I'm happy to comment it more thoroughly.

import com.rklaehn.radixtree.RadixTree

import scala.io.Source

import java.io.File

def fromFile(filename: String): RadixTree[String, Boolean] =

def fromLines(lines: Seq[String]): RadixTree[String, Boolean] = {
// we mark a target as a terminal by making the associated value true
// all substrings will not have a true value, so only exact matches
// are true
val pairs = lines.map(line => (line.toLowerCase, true))
}
}


final case class Match(filename: String, offset: Int, target: String) {
def hexOffset: String = offset.toHexString
}

class FileProcessor(private val filename: String, private val trie: RadixTree[String, Boolean]) {

private val charAndIndex: Iterator[(Char, Int)] = Source.fromFile(filename).zipWithIndex

private def isTarget(t: RadixTree[String, Boolean], prefix: String): Boolean =
t.getOrDefault(prefix.toLowerCase, false)

private def isEmptyWithPrefix(t: RadixTree[String, Boolean], prefix: String): Boolean = {
val subtrieKeys = trie.subtreeWithPrefix(prefix).keys
subtrieKeys.isEmpty || (subtrieKeys.size == 1 && subtrieKeys.head.isEmpty)
}

// this is the bottleneck -- all chars in sb were in the trie, but
// we are rechecking them each time.
// alternative is to pass a a trie into this, costing memory
private def processCurrent(matches: Seq[Match], sb: StringBuffer, c: Char, i: Int): (Seq[Match], StringBuffer) = {
sb.append(c)
val s = sb.toString.toLowerCase
(isTarget(trie, s), isEmptyWithPrefix(trie, s)) match {
case (true, true) => (matches :+ Match(filename, i - s.length, s), new StringBuffer)
case (true, false) => (matches :+ Match(filename, i - s.length, s), sb)
case (false, true) => (matches, new StringBuffer)
case _ => (matches, sb)
}
}

def findMatches: Seq[Match] = {
charAndIndex.foldLeft(Seq.empty[Match], new StringBuffer) { case ((acc, sb), (char, idx)) =>
processCurrent(acc, sb, char, idx)
}._1
}
}


class DirectoryProcessor(dir: String, targetFile: String) {

val files: Seq[File] = new File(dir) match {
case d if d.exists && d.isDirectory => d.listFiles.filter(_.isFile)
case _ => Nil
}
}

private val files = new DirectoryReader(dir).files

// Processing a file is read-only, so we can do this in parallel
def processDirectory: collection.parallel.ParSeq[Match] = files.par.map(f => new FileProcessor(f.getPath, trie))
.flatMap(_.findMatches)
}


Clearly I could remove unnecessary work by passing a trie (or subtrie) to FileProcessor#processCurrent where I'll traverse based on the current character, but I believe this would make the memory usage rather intractable for large enough tries.

Are there any easy optimizations that I've missed?

• You posted some code and asserted "it is slow". You chose not to profile it, or at least you chose not to share profiling results with us. Please describe which specific source lines account for the bulk of the processing time. We could guess, but it would be better to know. Also, if you have a unit test that exercises the code, I wouldn't say "no" to reading the test, especially if it relates to the profiling run. – J_H Aug 29 '17 at 4:21
• @JH I think I did you one better by addressing exactly why it's slow. From an algorithmic standpoint, I'm at a decision between speed and memory: recurse on expensive subtries, or recheck prefixes. – erip Aug 29 '17 at 10:21

# time complexity

There is one troubling call in processCurrent that jumps out at me - the downcasing. I get the sense that sb becomes "big", so the nested inner loop for the linear scan seems like trouble. It's the sort of thing that can easily turn e.g. a linear algorithm into a quadratic one. I understand that case matters for correctness, but just humor me for a moment. Imagine an alternate implementation that calls toLowerCase at file read time, destroying valuable information but allowing processCurrent to happen quicker. With such results in hand as a valuable hint, could you coax the current implementation to report results faster? As a simpler alternative, could we replace all comparisons in the current implementation with case-insensitive comparisons? Maybe downcase data when handing it to the radix tree library. The point is to avoid repeatedly downcasing a given character many thousands of times - we want to do localized work on our current focus rather than doing (ignored) global work.

# memory complexity

There are a few large memory consumers such as storing Match hexOffsets, and storing charAndIndex tuples rather than generating them. Their cost is "just" linear with filesize, so maybe it's an acceptable tradeoff in the name of clarity, but you might think about what the code would look like if you deleted a large ancillary object (or made it smaller). Perhaps code that depended on the large object could get by within a smaller footprint? You're memory constrained and you want parallelism, so reducing memory by 2x would let you keep twice as many cores busy.

## varying file sizes, and stragglers

The parallel mapping that invokes FileProcessor is very nice, it is simple and clear. But you complain about memory pressure, and I think your input files are of diverse sizes. This leads to two suggestions: consider viewing files as a series of fixed-length subproblems to work on, and consider throwing lots of tasks into a queue that a fixed number of worker bees draw from. Then you can size it so there's about N workers for N cores, each using about 1 / Nth of memory (either 1 / Nth of heap or 1 / Nth of cache, whichever matter more to your elapsed times). If the current code encounters a mix of files where the largest is, say, double the size of the smallest, then it's likely to be a straggler that impacts elapsed time while most of memory and most of cores are idle.

# style

Instead of trie, it would have been helpful to me if you had written private val targetTrie, parallel with targetFile which is a nice informative identifier. It would be very helpful to write down pre- & post-conditions that processCurrent maintains.

• Good eye on the toLowerCase calls. As a part of comparing times, I'm writing my own naive trie which cuts down on the toLowerCase calls and reading processing files uses iterators with filters and Character#toLowerCase calls. As for Match#toHexOffset -- this is generated rather than stored. The rest of the points are quite nice. Once my evaluation compared to my personal trie is completed, I might add it as an update to the original question or even a second answer. – erip Aug 30 '17 at 16:14
• "As for Match#toHexOffset -- this is generated rather than stored. " Oh, yeah. Cool! (And a 2nd answer would be a good thing.) – J_H Aug 30 '17 at 16:32

Swap a linear operation for a constant one

Currently the processCurrent function is appending (:+) Match objects to matches. matches is a Seq so this append operation has a complexity that is linear in the length of matches. You can remove this overhead by refactoring matches into a ListBuffer which can perform the append operation in constant time.

If you wish you can check out this link for more details on performance characteristics of various Scala collection.

A minor redundancy

It looks like you could remove the toLowerCase that occurs within isTarget because it is called immediately before on the same String object in processCurrent.