//! Uses dynamic programming to infer the location of spaces in a string without spaces.
#[macro_use]
extern crate cute;
#[macro_use]
extern crate lazy_static;
use std::{collections::HashMap, io};
use flate2::read::GzDecoder;
pub fn read_string<T: io::Read>(r: &mut T) -> Result<String, io::Error> {
let mut s = String::new();
r.read_to_string(&mut s).map(|_| s)
}
pub fn split(s: &str) -> Vec<&str> {
lazy_static! {
static ref DATA: String = read_string(&mut GzDecoder::new(&include_bytes!("../wordninja_words.txt.gz")[..]).unwrap()).unwrap();
// Build a cost dictionary, assuming Zipf's law and cost = -log(probability).
static ref WORDS: Vec<&'static str> = DATA.lines().collect::<Vec<_>>();
static ref WORDCOST: HashMap<&'static &'static str, f32> = c!{k => ((i + 1) as f32 * (WORDS.len() as f32).ln()).ln(), for (i, k) in WORDS.iter().enumerate()};
static ref MAXWORD: usize = WORDS.iter().map(|w| w.len()).max().unwrap();
}
// Find the best match for the i first characters, assuming cost has
// been built for the i-1 first characters.
// Returns a pair (match_cost, match_length).
let best_match = |cost: &[f32], i| {
use noisy_float::prelude::*;
use std::f32;
let candidates = cost[if i >= *MAXWORD { i - *MAXWORD } else { 0 }..i].iter().rev().enumerate();
candidates
.map(|(k, c)| (c + *WORDCOST.get(&&s[i - k - 1..i]).unwrap_or(&f32::INFINITY), k + 1))
.min_by_key(|&(c, _)| n32(c))
.unwrap()
};
// Build the cost array.
let mut cost = vec![0.];
for i in 0..s.len() {
let (c, _) = best_match(&cost, i + 1);
cost.push(c);
}
// Backtrack to recover the minimal-cost string.
let mut out = vec![];
let mut i = s.len();
while i > 0 {
let (c, k) = best_match(&cost, i);
assert_eq!(c, cost[i]);
out.insert(0, &s[i - k..i]);
i -= k;
}
out
}
#[test]
fn tests() {
fn check(s: &str, r: &[&str]) {
assert_eq!(split(s), r);
}
check("sensesworkingovertime", &["senses", "working", "overtime"]);
check("thumbgreenappleactiveassignmentweeklymetaphor", &[
"thumb",
"green",
"apple",
"active",
"assignment",
"weekly",
"metaphor",
]);
check(
"itwasadarkandstormynighttherainfellintorrentsexceptatoccasionalintervalswhenitwascheckedbyaviolentgustofwindwhichsweptupthestreetsforitisinlondonthatoursceneliesrattlingalongthehousetopsandfiercelyagitatingthescantyflameofthelampsthatstruggledagainstthedarkness",
&[
"it",
"was",
"a",
"dark",
"and",
"stormy",
"night",
"the",
"rain",
"fell",
"in",
"torrents",
"except",
"at",
"occasional",
"intervals",
"when",
"it",
"was",
"checked",
"by",
"a",
"violent",
"gust",
"of",
"wind",
"which",
"swept",
"up",
"the",
"streets",
"for",
"it",
"is",
"in",
"london",
"that",
"our",
"scene",
"lies",
"rattling",
"along",
"the",
"housetops",
"and",
"fiercely",
"agitating",
"the",
"scanty",
"flame",
"of",
"the",
"lamps",
"that",
"struggled",
"against",
"the",
"darkness",
],
);
check(
"thereismassesoftextinformationofpeoplescommentswhichisparsedfromhtmlbuttherearenodelimitedcharactersinthemforexamplethumbgreenappleactiveassignmentweeklymetaphorapparentlytherearethumbgreenappleetcinthestringialsohavealargedictionarytoquerywhetherthewordisreasonablesowhatsthefastestwayofextractionthxalot",
&[
"there",
"is",
"masses",
"of",
"text",
"information",
"of",
"peoples",
"comments",
"which",
"is",
"parsed",
"from",
"html",
"but",
"there",
"are",
"no",
"delimited",
"characters",
"in",
"them",
"for",
"example",
"thumb",
"green",
"apple",
"active",
"assignment",
"weekly",
"metaphor",
"apparently",
"there",
"are",
"thumb",
"green",
"apple",
"etc",
"in",
"the",
"string",
"i",
"also",
"have",
"a",
"large",
"dictionary",
"to",
"query",
"whether",
"the",
"word",
"is",
"reasonable",
"so",
"what",
"s",
"the",
"fastest",
"way",
"of",
"extraction",
"thx",
"a",
"lot",
],
);
}
It would also make sense to add a function to decompress the data before the first segmentation request, to reduce the wait time for the first segmentation request's result.
E.g. this function can be called in main()
and would just access the DATA
lazy static variable, to cause it to be evaluated.
(Or with once_cell
.)