<commit_before>#+TITLE: Cheno Stenography Outline
#+AUTHOR: <NAME>

* Introduction
  The main goal of Cheno is to provide a portable C library to help
  with writing stenography applications. Mainly the goal is to write
  code which can be executed on many different microcontrollers so
  that people can make good hardware stenotypes with minimal effort in
  software (if any), however people may use Cheno in more typical
  applications to do stenography related work. Whether you want to
  write an application like [[http://plover.stenoknight.com/][Plover]], or write something to translate
  logs of chords into actual words, Cheno should be able to help you!
** Goals
   There are several goals for Cheno

   - Run on as many cheap microcontrollers as possible.
   - Be lightweight
   - Allow for simple use in a variety of Stenography related applications.
* Dictionary Handling
  In order to run on the cheapest of microcontrollers Cheno must
  provide as lightweight of a dictionary as possible. The dictionary
  must support fast look ups (this is the primary concern), but
  insertions should also be as fast as possible because it will be
  useful should the user wish to add a word in real time. Deletion is
  probably a good idea as well, but I don't think it is necessary for
  it to be particularly speedy.

  Dictionaries will likely be stored on SD cards, and we may store
  them in raw blocks on the SD card instead of going through a file
  system. Using a simple FAT filesystem may be a good idea as it would
  easily allow for somebody to move dictionaries on and off of their
  SD card. However, it might be best to just use raw blocks and
  provide a program for storing this information on the SD card.

  SD card accesses are going to be expensive, so ideally we want to
  limit them as much as possible. We want as few SD card accesses per
  stroke as possible. This should be considered when designing the
  dictionary.

  In the future we might want to consider using Red-Black trees to
  store the dictionaries as they provide better guarantees about the
  performance than a naive binary tree. However, for simplicity we
  will start with the naive binary trees -- in fact there is a good
  chance that these will be sufficient.

  The current idea is to have a binary tree (possibly a fancy self
  balancing one) for each stroke. That is, we have a binary tree
  holding all of the possible first chords. Each node of this binary
  tree contains binary trees for the next possible chords (if
  any). The advantage of this is that we can keep track of the current
  index of our dictionary look up and then we only have to go one
  additional step in the dictonary's trees for each additional
  stroke. It then becomes trivial to find the next word, we either
  look up the next stroke from the current place, and if it's there we
  use that word. If it's not there we just start from the root of the
  tree again.

  We should store the parent node for each node as well. This will
  help when we need to do stuff with *. Thus for each node we need the
  following information:

  - Parent node.
  - Left and right children indices (these are for "same stroke" children).
  - Index for root of "next stroke" tree.
  - The stroke represented by the current node.
  - Perhaps some extra information (for instance Red / Black).
  - The actual text / length of text.

  We will use an index of 0 to represent node's which don't exist. I
  think 64 bytes is sufficient, and if need be the translation text
  can flow into a special "text" node adjacent to this.

  Defrag involves changing ids?

  64 byte blocks should usually be sufficient, and in the case that
  they are not the next block over will be used to store the text
  instead. In this case another SD card read is fairly unlikely as we
  will have read 512 bytes in at a time, and the next block is likely
  contained within this full SD card block. If it's not we will
  probably have at most one more SD card read, which should hopefully
  be fast enough for this to not matter.

  Might also be a good idea to have a special undo node, which stores
  the key strokes that are necessary to undo the stroke.
* Strokes
  In order to represent strokes Cheno will use 32-bit integers. The
  individual bits will represent each of the keys pressed on the
  stenotype for the given chord. Additionally some of the extra bits
  will be used for flags such as a "start of word" flag representing
  the first stroke when we switch to a new word. This representation
  will allow for a very small memory footprint, and should allow for
  easy manipulation / storage of the strokes.

  Bits should be in steno order, with the least significant bit
  representing the first character in the steno order. The number pad
  bit occurs after the others. Steno order is given by:

  : STKPWHRAO*EUFRPBLGTSDZ#
* Translation
  The "translation" that Cheno does relies upon dictionary look ups,
  and history in order to look up words in the dictionary. For single
  stroke words the look up is simply one to one for the current chord
  being pressed and the entry in the dictionary, however matters are
  complicated significantly by the fact that many words will actually
  use multiple strokes. Some issues arise:

  - How do we know when to break and decide we are starting on a new word?
  - How do we keep track of what the previous strokes for a multi-stroke word were?
  - How do we correct words when a second stroke involves changes to the current translation?
  - What about undo!?

  The most obvious means to handle this is by marking the first stroke
  as the "start stroke" of a word (for instance if we are representing
  each stroke with a 4 byte integer we could have one of the upper
  bits be a flag for this). Then for subsequent strokes we can go back
  to the start stroke, note all of the strokes from the "start stroke"
  to the latest stroke, and attempt to look up this sequence of
  strokes in the dictionary. If this multi-stroke is found in the
  dictionary we can use this translation, but otherwise we must mark
  the latest stroke as a "start stroke" and look up that stroke in the
  dictionary (if it has no dictionary entry we should just output the
  representation of the stroke). Informally, whenever we mark a "start
  stroke" this is the beginning of a new word / entry in the
  dictionary.

  In order to implement corrections (both undo and corrections for
  outputs from previous strokes in multi-stroke words) we will look
  for the last "start stroke" and perform the previous dictionary look
  up. We can then determine the length of the translation for the
  sequence of strokes and delete that many characters. If this is for
  an undo we should then delete the previous stroke from the history,
  and then output the dictionary look up for the current set of
  strokes. If this is for adding an additional stroke to a word we
  should add the stroke to the history and output the new translation.

  There may be a case where the dictionary has an entry for, say, a
  single stroke word and a three stroke word which start with the same
  strokes, but the middle stroke is also used in another word. In this
  case the dictionary should have an entry for the word at two strokes
  in the three stroke word. This entry will have a flag set that
  represents the fact that these two strokes aren't technically an
  entry in the dictionary, but there might be a larger one. In this
  case we shouldn't type anything, and wait for the next stroke. If
  the next stroke would create the three stroke word then everything
  continues as usual, however if we get to the point where there is no
  entry in this particular branch of the dictionary then we must
  backtrack to find the first set of strokes that actually had an
  entry, and we write that word -- this is the last stroke in the
  word, and the next stroke (we have to remember the other strokes) is
  a "start stroke".

  For corrections I don't think we should do anything complicated like
  figuring out the minimum number of characters we need to delete and
  replace. This will add unneeded complexity for something which is
  unlikely to provide any real performance benefit -- we can probably
  just blast the key presses over USB more than quickly enough for
  this to not matter in the slightest.
* History
  We need to be able to implement history. This is needed for
  translation, but history files may also be of use.
* Porting
  In order to port the dictionary you must write an appropriate
  index.h
* Issues
  - No way to know about focus. If the user switches between
    applications the history won't know that / be able to account for
    it with things like undo and multi-stroke words. We can maybe add
    special strokes to keep track of a focus switch (or they would at
    least appear in a history file so people could sort it out
    afterwards).<commit_msg>Some changes and additions to the plan.<commit_after>#+TITLE: Cheno Stenography Outline
#+AUTHOR: <NAME>

* Introduction
  The main goal of Cheno is to provide a portable C library to help
  with writing stenography applications. Mainly the goal is to write
  code which can be executed on many different microcontrollers so
  that people can make good hardware stenotypes with minimal effort in
  software (if any), however people may use Cheno in more typical
  applications to do stenography related work. Whether you want to
  write an application like [[http://plover.stenoknight.com/][Plover]], or write something to translate
  logs of chords into actual words, Cheno should be able to help you!
** Goals
   There are several goals for Cheno

   - Run on as many cheap microcontrollers as possible.
   - Be lightweight
   - Allow for simple use in a variety of Stenography related applications.
* Dictionary Handling
  In order to run on the cheapest of microcontrollers Cheno must
  provide as lightweight of a dictionary as possible. The dictionary
  must support fast look ups (this is the primary concern), but
  insertions should also be as fast as possible because it will be
  useful should the user wish to add a word in real time. Deletion is
  probably a good idea as well, but I don't think it is necessary for
  it to be particularly speedy.

  Dictionaries will likely be stored on SD cards, and we may store
  them in raw blocks on the SD card instead of going through a file
  system. Using a simple FAT filesystem may be a good idea as it would
  easily allow for somebody to move dictionaries on and off of their
  SD card. However, it might be best to just use raw blocks and
  provide a program for storing this information on the SD card.

  SD card accesses are going to be expensive, so ideally we want to
  limit them as much as possible. We want as few SD card accesses per
  stroke as possible. This should be considered when designing the
  dictionary.

  The current idea is to have a binary tree (Red-Black trees seem like
  a good choice, as they provide good guarantees, and are easily
  implemented) for each stroke. That is, we have a binary tree holding
  all of the possible first chords. Each node of this binary tree
  contains binary trees for the next possible chords (if any). The
  advantage of this is that we can keep track of the current index of
  our dictionary look up and then we only have to go one additional
  step in the dictonary's trees for each additional stroke. It then
  becomes trivial to find the next word, we either look up the next
  stroke from the current place, and if it's there we use that
  word. If it's not there we just start from the root of the tree
  again.

  We should store the parent node for each node as well. This will
  help when we need to do stuff with *. Thus for each node we need the
  following information:

  - Parent node.
  - Left and right children indices (these are for "same stroke" children).
  - Index for root of "next stroke" tree.
  - The stroke represented by the current node.
  - Perhaps some extra information (for instance Red / Black).
  - The actual text / length of text.

  We will use an index of 0 to represent node's which don't exist. I
  think 64 bytes is sufficient, and if need be the translation text
  can flow into a special "text" node adjacent to this.

  Defrag involves changing ids?

  64 byte blocks should usually be sufficient, and in the case that
  they are not the next block over will be used to store the text
  instead. In this case another SD card read is fairly unlikely as we
  will have read 512 bytes in at a time, and the next block is likely
  contained within this full SD card block. If it's not we will
  probably have at most one more SD card read, which should hopefully
  be fast enough for this to not matter.

  Might also be a good idea to have a special undo node, which stores
  the key strokes that are necessary to undo the stroke. For instance
  if you have a chord which runs the undo command on an application
  (the usual ctl + z), then maybe it makes sense to have the stenotype
  run the redo command when undoing this stroke.
* Strokes
  In order to represent strokes Cheno will use 32-bit integers. The
  individual bits will represent each of the keys pressed on the
  stenotype for the given chord. Additionally some of the extra bits
  will be used for flags such as a "start of word" flag representing
  the first stroke when we switch to a new word. This representation
  will allow for a very small memory footprint, and should allow for
  easy manipulation / storage of the strokes.

  Bits should be in steno order, with the least significant bit
  representing the first character in the steno order. The number
  bar's bit occurs after the others. Steno order is given by:

  : STKPWHRAO*EUFRPBLGTSDZ#
* Translation
  The "translation" that Cheno does relies upon dictionary look ups,
  and history in order to look up words in the dictionary. For single
  stroke words the look up is simply one to one for the current chord
  being pressed and the entry in the dictionary, however matters are
  complicated significantly by the fact that many words will actually
  use multiple strokes. Some issues arise:

  - How do we know when to break and decide we are starting on a new word?
  - How do we keep track of what the previous strokes for a multi-stroke word were?
  - How do we correct words when a second stroke involves changes to the current translation?
  - What about undo!?

  The most obvious means to handle this is by marking the first stroke
  as the "start stroke" of a word (for instance if we are representing
  each stroke with a 4 byte integer we could have one of the upper
  bits be a flag for this). Then for subsequent strokes we can go back
  to the start stroke, note all of the strokes from the "start stroke"
  to the latest stroke, and attempt to look up this sequence of
  strokes in the dictionary. If this multi-stroke is found in the
  dictionary we can use this translation, but otherwise we must mark
  the latest stroke as a "start stroke" and look up that stroke in the
  dictionary (if it has no dictionary entry we should just output the
  representation of the stroke). Informally, whenever we mark a "start
  stroke" this is the beginning of a new word / entry in the
  dictionary.

  In order to implement corrections (both undo and corrections for
  outputs from previous strokes in multi-stroke words) we will look
  for the last "start stroke" and perform the previous dictionary look
  up. We can then determine the length of the translation for the
  sequence of strokes and delete that many characters. If this is for
  an undo we should then delete the previous stroke from the history,
  and then output the dictionary look up for the current set of
  strokes. If this is for adding an additional stroke to a word we
  should add the stroke to the history and output the new translation.

  There may be a case where the dictionary has an entry for, say, a
  single stroke word and a three stroke word which start with the same
  strokes, but the middle stroke is also used in another word. In this
  case the dictionary should have an entry for the word at two strokes
  in the three stroke word. This entry will have a flag set that
  represents the fact that these two strokes aren't technically an
  entry in the dictionary, but there might be a larger one. In this
  case we shouldn't type anything, and wait for the next stroke. If
  the next stroke would create the three stroke word then everything
  continues as usual, however if we get to the point where there is no
  entry in this particular branch of the dictionary then we must
  backtrack to find the first set of strokes that actually had an
  entry, and we write that word -- this is the last stroke in the
  word, and the next stroke (we have to remember the other strokes) is
  a "start stroke".

  For corrections I don't think we should do anything complicated like
  figuring out the minimum number of characters we need to delete and
  replace. This will add unneeded complexity for something which is
  unlikely to provide any real performance benefit -- we can probably
  just blast the key presses over USB more than quickly enough for
  this to not matter in the slightest.
* History
  We need to be able to implement history. This is needed for
  translation, but history files may also be of use.
* Porting
  In order to port the dictionary you must write an appropriate
  index.h
* Issues
  - No way to know about focus. If the user switches between
    applications the history won't know that / be able to account for
    it with things like undo and multi-stroke words. We can maybe add
    special strokes to keep track of a focus switch (or they would at
    least appear in a history file so people could sort it out
    afterwards). We could have a number of different focuses, and
    select between them with the number bar.
{'fraction_non_alphanumeric': 0.025994223505887582, 'fraction_numerical': 0.001221950677627194, 'mean_word_length': 3.5352644836272042, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3569726', 'n_tokens_mistral': 4470, 'n_tokens_neox': 4288, 'n_words': 3076}