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