lt-proc -b explodes on a-zA-Z regexes + long input about lttoolbox HOT 5 OPEN

Another thing we could do is within State::step() record each (src, trg) pair for the main symbol and then skip any alt step that would be between the same pair. (Though we'd probably want to check whether that noticeably slowed anything down.)

from lttoolbox.

Each time you step by an uppercase letter, it also steps by the lowercase version, so for an N-letter word, you have 2^N states when you reach the end.

from lttoolbox.

Oh the reason we only see one result is that if it's not dictionaryCase, we apply input casing to each result, and they're merged into one.

$ echo BADGER | lt-proc --dictionary-case a.bin
^BADGER/baDGER<guess>/bADGEr<guess>/bADGeR<guess>/bADGer<guess>/bADgER<guess>/bADgEr<guess>/bADgeR<guess>/bADger<guess>/bAdGER<guess>/bAdGEr<guess>/bAdGeR<guess>/bAdGer<guess>/bAdgER<guess>/bAdgEr<guess>/bAdgeR<guess>/bAdger<guess>/bADGER<guess>/baDGEr<guess>/baDGeR<guess>/baDGer<guess>/baDgER<guess>/baDgEr<guess>/baDgeR<guess>/baDger<guess>/badGER<guess>/badGEr<guess>/badGeR<guess>/badGer<guess>/badgER<guess>/badgEr<guess>/badgeR<guess>/badger<guess>/BaDGER<guess>/BADGEr<guess>/BADGeR<guess>/BADGer<guess>/BADgER<guess>/BADgEr<guess>/BADgeR<guess>/BADger<guess>/BAdGER<guess>/BAdGEr<guess>/BAdGeR<guess>/BAdGer<guess>/BAdgER<guess>/BAdgEr<guess>/BAdgeR<guess>/BAdger<guess>/BADGER<guess>/BaDGEr<guess>/BaDGeR<guess>/BaDGer<guess>/BaDgER<guess>/BaDgEr<guess>/BaDgeR<guess>/BaDger<guess>/BadGER<guess>/BadGEr<guess>/BadGeR<guess>/BadGer<guess>/BadgER<guess>/BadgEr<guess>/BadgeR<guess>/Badger<guess>$

I feel like it should be possible to do some filtering earlier. We're looping back to the same FST-node over and over again:

but fst_processor doesn't just keep track of the Node, but also the sequence leading up to it:

  struct TNodeState
  {
    Node *where;
    std::vector<std::pair<int, double>> *sequence;
    // a state is "dirty" if it was introduced at runtime (case variants, etc.)
    bool dirty;

Would it be possible to filter out ones where the node is the same and the last part of the sequence differs?

Alternatively when doing step/apply, could we check if the result is the same, and never use the tolower(val) (alt) if they end up in the same Node? It wouldn't be a general solution, but would help in the common case of a-zA-Z.

from lttoolbox.

Another option, which I think we should do regardless (to prevent me from DoS-ing our servers with bad regexes), is have a max state size. As soon as you go over about 2^16 states you can feel the slowdown for a single (long, uppercase) word (and you're bound to be getting so many results it's mostly garbage), so perhaps simply

diff --git a/lttoolbox/fst_processor.cc b/lttoolbox/fst_processor.cc
index 1466ffb..98caea7 100644
--- a/lttoolbox/fst_processor.cc
+++ b/lttoolbox/fst_processor.cc
@@ -1087,7 +1087,7 @@ FSTProcessor::analysis(InputFile& input, UFILE *output)
     }
     else
     {
-      current_state.step_case(val, caseSensitive);
+      current_state.step_case(val, caseSensitive || current_state.size() >= 65536);
     }
 
     if(current_state.size() != 0)
@@ -2277,7 +2277,7 @@ FSTProcessor::bilingual(InputFile& input, UFILE *output, GenerationMode mode)
       }
       if(current_state.size() != 0)
       {
-        current_state.step_case(val, caseSensitive);
+        current_state.step_case(val, caseSensitive || current_state.size() >= 65536);
       }
       if(current_state.isFinal(all_finals))
       {

Maybe with a warning the first time we reach that size.

from lttoolbox.

when doing step/apply, could we check if the result is the same, and never use the tolower(val) (alt) if they end up in the same Node?

@ftyers can you imagine anywhere we would want a lowercase character (on the output-side) if input was upper and upper is possible and we end up in the same FST node? (That'd be like if you had both "iphone" and "iPhone" in your dix and user wrote "iPhone" – analysis would now only give "iPhone" instead of both. I would see that as a good thing, but maybe there are use-cases for having both.)

from lttoolbox.