<p>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.</p>

<p>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.  </p>

<p>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%.  </p>

CC BY-SA 3.0
2017-04-21T18:14:32.390Z
2017-04-21T18:14:32.390Z
KWillets
<p>A very simple questions. Let B be the <a href="https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" rel="nofollow noreferrer">BWT</a> (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?</p>

<p>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):</p>

<p>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)? </p>

CC BY-SA 3.0
2017-04-19T07:34:32.367Z
What's BWT? Please define.
Aryeh
CC BY-SA 3.0
2017-04-19T08:14:52.940Z
Please do not ask multiple questions per post.
Jan Johannsen
CC BY-SA 3.0
2017-04-22T00:20:46.783Z
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.
Jouni Sirén
<string-matching><string-search>
BWT: is it possible to predict the next character in a sequence?
user45031
# BWT: is it possible to predict the next character in a sequence?

(Asked by: username_0 on 2017-04-19)

A very simple questions. Let B be the [BWT](https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform) (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)?

**Tags:** string-matching, string-search

> **Comments:**
> **username_1**: What's BWT? Please define.  
> **username_2**: Please do not ask multiple questions per post.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2017-04-21. Score: 1

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%.


---

