seqalign/lib.rs
1//! Sequence alignment
2//!
3//! This crate implements commonly-used sequence alignment methods based on
4//! edit operations. There are multiple crates available to compute edit
5//! distances. However, to my knowledge there was no crate that supports
6//! all of the following seqalign features:
7//!
8//! * Works on slices of any type.
9//! * Can return both the edit distance and the edit script/alignment.
10//! * Can be extended with new measures.
11//!
12//! # Example
13//!
14//! ```
15//! use seqalign::Align;
16//! use seqalign::measures::LevenshteinDamerau;
17//!
18//! let incorrect = &['t', 'p', 'y', 'o'];
19//! let correct = &['t', 'y', 'p', 'o', 's'];
20//!
21//! let measure = LevenshteinDamerau::new(1, 1, 1, 1);
22//! let alignment = measure.align(incorrect, correct);
23//!
24//! // Get the edit distance
25//! assert_eq!(2, alignment.distance());
26//!
27//! // Get the edit script.
28//! use seqalign::measures::LevenshteinDamerauOp;
29//! use seqalign::op::IndexedOperation;
30//!
31//! assert_eq!(vec![
32//! IndexedOperation::new(LevenshteinDamerauOp::Match, 0, 0),
33//! IndexedOperation::new(LevenshteinDamerauOp::Transpose(1), 1, 1),
34//! IndexedOperation::new(LevenshteinDamerauOp::Match, 3, 3),
35//! IndexedOperation::new(LevenshteinDamerauOp::Insert(1), 4, 4)
36//! ], alignment.edit_script());
37//! ```
38
39#[cfg(test)]
40#[macro_use]
41extern crate lazy_static;
42
43#[cfg(test)]
44#[macro_use]
45extern crate maplit;
46
47#[cfg(test)]
48#[macro_use]
49extern crate pretty_assertions;
50
51mod dynprog;
52pub use crate::dynprog::{Align, Alignment};
53
54pub mod measures;
55
56pub mod op;
57
58/// Trait for edit distance measures.
59pub trait Measure<T> {
60 /// The edit operations associated with the measure.
61 type Operation: op::Operation<T>;
62
63 /// Get a slice with the measure's operations. Typically, this contains
64 /// all the enum variants of the associated type `Operation`.
65 fn operations(&self) -> &[Self::Operation];
66}
67
68/// A pairing of two sequences.
69pub struct SeqPair<'a, T> {
70 pub source: &'a [T],
71 pub target: &'a [T],
72}