1
$\begingroup$

A very simple questions. Let B be the BWT (Burrows–Wheeler transform) of a string S. My question is, due to "grouping" of consecutive characters in BWT, is it possible to somehow know the number of equal characters that follow given the first character of its kind (or at least some lower bound on the number of such characters). So let say B=...caaaaabaccccccacc... then, is it possible to know that after the first a there will be at least 2 consecutive a's or maybe the exact number of a's that follow?

Or alternatively one can pose a complementary question, a flip side of the above question (I write the question in order to better describe the problem):

Is there a better way to find breaks in BWT aside from checking each character and comparing it with the previous one. That is, let say I want to locate "ab" break. I would need to go from left to right and compare second character with the first one and then third with the second and so on until I find out where the pair mismatches. Is there a way to check every second character and come to the same result, because if this is possible then there exist a lower bound on the number of same consecutive characters (which is 2)?

$\endgroup$
  • 1
    $\begingroup$ What's BWT? Please define. $\endgroup$ – Aryeh Apr 19 '17 at 7:34
  • 1
    $\begingroup$ Please do not ask multiple questions per post. $\endgroup$ – Jan Johannsen Apr 19 '17 at 8:14
  • $\begingroup$ I get the feeling that you are asking the wrong question. You might not be trying to find runs or breaks, but to use them to solve a higher-level problem. There may be a BWT-based algorithm for the higher-level problem, but it will probably not work in the way you expect. $\endgroup$ – Jouni Sirén Apr 22 '17 at 0:20
1
$\begingroup$

In general, no, but it's difficult to prove a negative given that there might be some data structure equivalent to a BWT that provides the prediction capability.

The L vector in the BWT is simply a list of the input string's characters sorted by their following context, i.e. the suffix that begins immediately after each character. Its information content is inversely related to how well this following context predicts the character preceding it.

This predicability is present in many types of text and in many models for generating text, but it's easy to fool adversarially if you have some algorithm like you describe in your second paragraph. For instance, if your algorithm has only read a portion of the input (you don't specify how it operates, so I'm guessing), I believe it's possible to extend a string in such a way as to spoil any context where you think the prediction is 100%.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.