3
\$\begingroup\$

I am developing a FSM to segment Thai syllables with the following rules:

enter image description here

Here are my util functions:

package edu.washington.rippeth.ling473

package object proj3 {

  private[proj3] def optionallyAppend(sb: StringBuilder, char: Option[Char]): StringBuilder = char match {
    case Some(c) =>
      sb.append(c)
      sb
    case None =>
      sb
  }

  /** Inserts a space before the last element.
    *
    * @param sb the string to which a space should be added
    * @return the string with a space at the n-1st position
    */
  private[proj3] def addSpaceBeforeLast(sb: StringBuilder): StringBuilder = {
    sb.insert(sb.length-1, ' ')
    sb
  }

  /** Appends a space to the StringBuilder.
    *
    * @param sb the StringBuilder to which a space should be added
    * @return the StringBuilder with a space at the end
    */
  private[proj3] def addSpaceAtEnd(sb: StringBuilder): StringBuilder = {
    sb.append(' ')
    sb
  }

}

Here are my states:

package edu.washington.rippeth.ling473.proj3

private[proj3] sealed trait State {
  /**
    * The string builder before a character is potentially applied.
    */
  protected def stringBuilderIn: StringBuilder

  /**
    * The character which can trigger an update in state.
    *
    * Creating an Option[Char] is a hack because the empty char literal does not
    * exist in Scala.
    */
  protected def char: Option[Char]

  /**
    * An optional function which can transform the tape after the string builder
    * may have been updated. This will be `None` in the normal case.
    */
  protected def postProcessesStringBuilder: Option[StringBuilder => StringBuilder]

  /**
    * If the state is a "normal" state
    * @return
    */
  def stringBuilderOut: StringBuilder = postProcessesStringBuilder match {
      case Some(f) => f(optionallyAppend(stringBuilderIn, char))
      case None => optionallyAppend(stringBuilderIn, char)
    }
}

private[proj3] sealed trait NormalState extends State {
  /**
    * In the normal case, we don't post process the string builder -- potentially adding
    * the character is good enough.
    * @return
    */
  final protected def postProcessesStringBuilder: Option[StringBuilder => StringBuilder] = None
}

private[proj3] sealed trait StateWithPenultimateSpace extends State {
  /**
    * In state 7 and 8, a space is to be added before the penultimate character,
    * so this will be the post-processing function.
    */
  final protected def postProcessesStringBuilder: Option[StringBuilder => StringBuilder] =
    Some(addSpaceBeforeLast)
}

private[proj3] sealed trait StateWithFinalSpace extends State {
  /**
    * In state 9, a space is to be appended to the string, so this will be
    * the post-processing function.
    */
  final protected def postProcessesStringBuilder: Option[StringBuilder => StringBuilder] =
    Some(addSpaceAtEnd)
}

// State0 through State6 are very vanilla -- just appending
// a character to the output string
private[proj3] final case class State0(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState
private[proj3] final case class State1(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState
private[proj3] final case class State2(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState
private[proj3] final case class State3(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState
private[proj3] final case class State4(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState
private[proj3] final case class State5(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState
private[proj3] final case class State6(stringBuilderIn: StringBuilder, char: Option[Char])
  extends NormalState

// State7 and State8 are special -- add a space before the last character
// in the output string
private[proj3] final case class State7(stringBuilderIn: StringBuilder, char: Option[Char])
  extends StateWithPenultimateSpace
private[proj3] final case class State8(stringBuilderIn: StringBuilder, char: Option[Char])
  extends StateWithPenultimateSpace

// State9 is also special -- add a space to the end of the output string
private[proj3] final case class State9(stringBuilderIn: StringBuilder, char: Option[Char])
  extends StateWithFinalSpace

And here is my state machine:

package edu.washington.rippeth.ling473.proj3

import com.typesafe.scalalogging.LazyLogging

/** Given input lines, moves through the state machine for
  * each line
  *
  * @param lines the unsegmented Thai lines
  */
class StateMachine(lines: Iterable[String]) extends LazyLogging {

  // The categories that force transitions
  private final val V1: Set[Char] = "เแโใไ".toSet
  private final val C1: Set[Char] = "กขฃคฅฆงจฉชซฌญฎฏฐฑฒณดตถทธนบปผฝพฟภมยรฤลฦวศษสหฬอฮ".toSet
  private final val C2: Set[Char] = "รลวนม".toSet
  private final val V2: Set[Char] = "◌ิ◌ี◌ึ◌ื◌ุ◌ู◌ั◌็".toSet
  private final val T: Set[Char] = Set('\u0E48', '\u0E49', '\u0E4A', '\u0E4B')
  private final val V3: Set[Char] = "าอยว".toSet
  private final val C3: Set[Char] = "งนมดบกยว".toSet

  // The following methods define the actions to be performed
  // (i.e., defining to which state the machine should transition)
  // The naming convention is actionN where N is the state before
  // transition

  private def action0(implicit oldState: State, c: Char): State =
    if(V1.contains(c)) {
      logger.trace("Going to state 1")
      State1(oldState.stringBuilderOut, Some(c))
    } else if(C1.contains(c)) {
      logger.trace("Going to state 2")
      State2(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  private def action1(oldState: State, c: Char): State =
    if(C1.contains(c)) {
      logger.trace("Going to state 2")
      State2(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  private def action2(oldState: State, c: Char): State =
    if(C2.contains(c)) {
      logger.trace("Going to state 3")
      State3(oldState.stringBuilderOut, Some(c))
    } else if(V2.contains(c)) {
      logger.trace("Going to state 4")
      State4(oldState.stringBuilderOut, Some(c))
    } else if(T.contains(c)) {
      logger.trace("Going to state 5")
      State5(oldState.stringBuilderOut, Some(c))
    } else if(V3.contains(c)) {
      logger.trace("Going to state 6")
      State6(oldState.stringBuilderOut, Some(c))
    } else if(C3.contains(c)) {
      logger.trace("Going to state 9")
      State9(oldState.stringBuilderOut, Some(c))
    } else if(V1.contains(c)) {
      logger.trace("Going to state 7")
      State7(oldState.stringBuilderOut, Some(c))
    } else if(C1.contains(c)) {
      logger.trace("Going to state 8")
      State8(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  private def action3(oldState: State, c: Char): State =
    if(V2.contains(c)) {
      logger.trace("Going to state 4")
      State4(oldState.stringBuilderOut, Some(c))
    } else if(T.contains(c)) {
      logger.trace("Going to state 5")
      State5(oldState.stringBuilderOut, Some(c))
    } else if(V3.contains(c)) {
      logger.trace("Going to state 6")
      State6(oldState.stringBuilderOut, Some(c))
    } else if(C3.contains(c)) {
      logger.trace("Going to state 9")
      State9(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  private def action4(oldState: State, c: Char): State =
    if(T.contains(c)) {
      logger.trace("Going to state 5")
      State5(oldState.stringBuilderOut, Some(c))
    } else if(V3.contains(c)) {
      logger.trace("Going to state 6")
      State6(oldState.stringBuilderOut, Some(c))
    } else if(C3.contains(c)) {
      logger.trace("Going to state 9")
      State9(oldState.stringBuilderOut, Some(c))
    } else if(V1.contains(c)) {
      logger.trace("Going to state 7")
      State7(oldState.stringBuilderOut, Some(c))
    } else if(C1.contains(c)) {
      logger.trace("Going to state 8")
      State8(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  private def action5(oldState: State, c: Char): State =
    if(V3.contains(c)) {
      logger.trace("Going to state 6")
      State6(oldState.stringBuilderOut, Some(c))
    } else if(C3.contains(c)) {
      logger.trace("Going to state 9")
      State9(oldState.stringBuilderOut, Some(c))
    } else if(V1.contains(c)) {
      logger.trace("Going to state 7")
      State7(oldState.stringBuilderOut, Some(c))
    } else if(C1.contains(c)) {
      logger.trace("Going to state 8")
      State8(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  private def action6(oldState: State, c: Char): State =
    if(C3.contains(c)) {
      logger.trace("Going to state 9")
      State9(oldState.stringBuilderOut, Some(c))
    } else if(V1.contains(c)) {
      logger.trace("Going to state 7")
      State7(oldState.stringBuilderOut, Some(c))
    } else if(C1.contains(c)) {
      logger.trace("Going to state 8")
      State8(oldState.stringBuilderOut, Some(c))
    } else
      throw new IllegalArgumentException(s"Invalid input '$c'")

  // Because actions 7, 8, and 9 don't consume input,
  // they will simply be a pass-through to the action of the
  // state for which they are acting as a proxy
  private def action7(oldState: State, c: Char): State = action1(oldState, c)
  private def action8(oldState: State, c: Char): State = action2(oldState, c)
  private def action9(oldState: State, c: Char): State = action0(oldState, c)

  /** Given a state and a character, choose the next action to perform
    * (i.e., choose the next state)
    *
    * @param state the state of the machine right now
    * @param c the character triggering a transition
    * @return the new state of the machine
    */
  private def segmentationFunction(state: State, c: Char): State = state match {
    case s: State0 => action0(s, c)
    case s: State1 => action1(s, c)
    case s: State2 => action2(s, c)
    case s: State3 => action3(s, c)
    case s: State4 => action4(s, c)
    case s: State5 => action5(s, c)
    case s: State6 => action6(s, c)
    case s: State7 => action7(s, c)
    case s: State8 => action8(s, c)
    case s: State9 => action9(s, c)
  }

  logger.trace("In state 0")
  private final def initialState: State = State0(new StringBuilder, None)

  /** For a given line, this function will work through
    *  the entire transition of state in the state machine.
    *
    * @param line the line being processed
    * @return the final state
    */
  private def transition(line: String, initialState: State): State = {
    // Given a state (with initial value of State0(new StringBuilder)) and a character
    // (left to right in the string), apply segmentationFunction. Update
    // the state and move to next character in the line.
    val state = line.foldLeft(initialState) { (state, c) =>
      logger.trace(s"Handling $c")
      segmentationFunction(state, c)
    }
    logger.debug(s"Processed line: ${state.stringBuilderOut.toString()}")
    state
  }

  /** Apply transition to the given line and return the output string from
    * the resultant state
    *
    * @param line the line being processed
    * @return the output string of the final state
    */
  private def segmentLine(line: String): String = transition(line, initialState).stringBuilderOut.toString

  /** Segments all lines
    *
    * @return the SegmentedLines of all the inputs
    */
  def segmentLines: SegmentedLines = new SegmentedLines(lines.map(segmentLine))
}

Here, SegmentedLines is just a class that will transform the output into a standard form -- it is beyond the scope of the review, but for completeness, it's below:

package edu.washington.rippeth.ling473.proj3

import java.io.{BufferedWriter, File, FileWriter}

class SegmentedLines(l: Iterable[String]) {

  /** The trimmed input lines in case an extra space appears at the end
    * of the lines
    *
    */
  val lines: Iterable[String] = l.map(_.trim)

  /** Converts lines to a newline-delimited string of lines each ending with a
    * break element
    *
    * @return
    */
  private def htmlifiedLines: String = lines.map(_ + "<br />").mkString("\n")

  /** Converts the cleaned lines to an HTML string
    *
    * @return HTML stringified output lines
    */
  override def toString: String =
    s"""<html>
      |<meta http-equiv='Content-Type' content='text/html; charset=UTF-8' />
      |<body>
      |$htmlifiedLines
      |</body>
      |</html>""".stripMargin

  /** Writes the HTML stringified lines to a file
    *
    * @param filename the name of the output file
    */
  def toHtmlFile(filename: String): Unit = {
    val file = new File(filename)
    val bw = new BufferedWriter(new FileWriter(file))
    bw.write(this.toString)
    bw.close()
  }
}

My tests are here:

package edu.washington.rippeth.ling473.proj3

import org.scalatest.FlatSpec

class StateMachineTest extends FlatSpec {

  "A StateMachine" should "segment the example" in {

    val input: Seq[String] = Seq("แบ่งแผ่นดินออกเป็นสองสว่น", "หลุมพอต้นใหญ่งอกงามชิดตลิ่ง")
    val expectedOutput = Seq("แบ่ง แผ่น ดิน ออก เป็น สอง สว่น", "หลุม พอ ต้น ให ญ่ง อก งาม ชิด ตลิ่ง")
    val stateMachine: StateMachine = new StateMachine(input)

    assertResult(expectedOutput) {
      stateMachine.segmentLines.lines
    }
  }

}

and

package edu.washington.rippeth.ling473.proj3

import org.scalatest.{Matchers, WordSpecLike}

class UtilsSpec extends WordSpecLike with Matchers {

  private def withCleanStringBuilder(block: StringBuilder => Any): Unit = {
    val sb = new StringBuilder
    block(sb)
  }

  "optionallyAppend" should {
    "append when the character is not None" in withCleanStringBuilder { sb =>
      sb shouldBe empty
      val charToAdd = 'c'
      val char @ Some(c) = Some(charToAdd)
      val newSb = optionallyAppend(sb, char)
      newSb.length should===(1)
      newSb.headOption shouldBe char
    }

    "not append when the character is None" in withCleanStringBuilder { sb =>
      sb shouldBe empty
      val char = None
      val newSb = optionallyAppend(sb, char)
      newSb shouldBe empty
    }
  }

  "addSpaceBeforeLast" should {
    "add a space before the last character" in withCleanStringBuilder { sb =>
      val (first, last) = ("hell", "o")
      val totalLength = first.length + last.length
      sb.appendAll(s"$first$last")
      val newSb = addSpaceBeforeLast(sb)
      // Added a space, so length is updated
      newSb.length should===(totalLength + 1)
      val expectedString = s"$first $last"
      newSb.toString should===(expectedString)
    }
  }

  "addSpaceAtEnd" should {
    "add a space at the last character" in withCleanStringBuilder { sb =>
      val expectedString = "hello "
      sb.appendAll(expectedString.trim)
      val newSb = addSpaceAtEnd(sb)
      newSb.toString should===(expectedString)
    }
  }

}

I'm interested in simplifying the states if possible and also general best practices. This implementation is fast enough™, but any performance improvements would be helpful (though I don't expect crazy benchmarking).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.