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

object RadixTreeReader {
  def fromFile(filename: String): RadixTree[String, Boolean] =
    RadixTreeReader.fromLines(Source.fromFile(filename).getLines().toSeq)

  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 =&gt; (line.toLowerCase, true))
    RadixTree[String, Boolean](pairs: _*)
  }
}




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 &amp;&amp; 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) =&gt; (matches :+ Match(filename, i - s.length, s), new StringBuffer)  
      case (true, false) =&gt; (matches :+ Match(filename, i - s.length, s), sb)
      case (false, true) =&gt; (matches, new StringBuffer)
      case _ =&gt; (matches, sb)
    }
  }

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




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

  private class DirectoryReader(dir: String) {
    val files: Seq[File] = new File(dir) match {
      case d if d.exists &amp;&amp; d.isDirectory =&gt; d.listFiles.filter(_.isFile)
      case _ =&gt; Nil
    }
  }

  private val files = new DirectoryReader(dir).files

  private val trie: RadixTree[String, Boolean] = RadixTreeReader.fromFile(targetFile)

  // Processing a file is read-only, so we can do this in parallel
  def processDirectory: collection.parallel.ParSeq[Match] = files.par.map(f =&gt; 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?
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- &amp; post-conditions that processCurrent maintains.