Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Small typo in WFA paper #24

Open
RagnarGrootKoerkamp opened this issue Jul 13, 2022 · 5 comments
Open

Small typo in WFA paper #24

RagnarGrootKoerkamp opened this issue Jul 13, 2022 · 5 comments

Comments

@RagnarGrootKoerkamp
Copy link
Contributor

RagnarGrootKoerkamp commented Jul 13, 2022

We're getting into very nitpicky things now, but I noticed this, and who knows, maybe you can still fix it for some future version 😄 :

  • Equation 3 in the WFA paper is missing some commas in the 2nd line, in the maximum for M^{lo}.
  • Edit: thinking more about it, maybe the max in that line should be min instead?
  • The pseudocode has $\widetilde M$ while the text has $\tilde M$.
@smarco
Copy link
Owner

smarco commented Aug 1, 2022

Hi, Ragnar.

Thanks for your comments. Obviously, I cannot easily change them in the published version, but I can change them in my latex version and upload them to Github.

Equation 3 in the WFA paper is missing some commas in the 2nd line, in the maximum for M^{lo}.

Surprisingly, these commas appear in my version (not in the editorial version, though).

Edit: thinking more about it, maybe the max in that line should be min instead?

That is correct. Following the implementation, it should be a min.

The pseudocode has ...

I never understood what happened there. In my latex, all were $\widetilde{M}$. Something got really wrong during the final editorial step.

Anyway, thanks for the corrections.

@smarco smarco closed this as completed Aug 1, 2022
@ksahlin
Copy link

ksahlin commented Sep 12, 2022

To continue the nitpicking.

In Algorithm 1, function header, I'm guessing it should be WF_ALIGN(q,t,p), i.e. lowercase p where it is the set of penalties. Also, the WF_NEXT function call and header should ideally have p as an argument.

In Algorithm 2 in the WFA paper, it should probably be while q[v] == t[h] (p is undefined in this context).

(I'm posting partly for documentation purposes but also to catch any misunderstandings I may have.)

@RagnarGrootKoerkamp
Copy link
Contributor Author

In that case, p (or o/e/x) should probably be passed to WF_NEXT as well, since currently algorithm 1 does not actually use p.

@ksahlin
Copy link

ksahlin commented Sep 13, 2022

First, I like to point out that WFA is a beautiful algorithm. Glad that I finally have some time to learn it in depth. Since this is an influential algorithm, it's important to get the details right if presented in other materials such as lectures etc.

Now that said. I have some further questions and comments on Algorithm 4 in the WFA paper for pruning the search.

  1. $left_v = |p| - (offset -k)$. I assume this should be $left_v = |q| - (offset -k)$
  2. $distance_k$, I assume this should be $d_k$ defined on the row above.
  3. Does $\widetilde{M}^{lo}$ and $\widetilde{M}^{hi}$ mean the global highest and lowest offsets over all $s$? Because these offset pointers sometimes are treated individually for each $s$, e.g. in Eq 3?
  4. When parsing algorithm 4 it is not immediately clear (to me) what $offset$ is in this function, could it be expressed from quantities defined in the function? I assume the for loop containing the $offset$-variable computes the number of vertical and horisontal steps to the 'end of the rectangle', respectively, and take the maximum of them. This is then the distance for the given point 'on the wave' to the end cell.
  5. Are each $d_k$ stored (e.g. in a vector) once computed in the for loop? I have this question because I wonder how the $d_{\widetilde{M}^{lo}}$ and $d_{\widetilde{M}^{hi}}$) are retrieved later in the while loop for pruning.

@smarco smarco reopened this Apr 24, 2023
@smarco
Copy link
Owner

smarco commented Apr 24, 2023

This ticket should be open. Thanks for your comments @ksahlin. Let me address these questions/comments as soon as possible.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants