Скажем, у вас есть предопределенный набор из n строк S = {s1, s2, ... sn}. Существует ли какой-нибудь эффективный алгоритм для определения подмножества S 'в S, такой, что concat (S') оптимально покрывает некоторую входную строку R? Оптимально я имею в виду что-то вроде некоторой комбинации наименьшего размера S 'и наименьшего расстояния редактирования между concat (S') и R.
Я считаю, что это должно быть похоже на разбиение слов на морфемы, но гдеморфемы - произвольное множество. Например, если S = {'pre', 'post', 'ing', 'heat'} и R 'притворяется', то S '= {' pre ',' ing '}, а если R «подогревает», тоS '= {' предварительно», 'тепло', 'ING'}.
Я пытался найти токенизаторы и морфологические анализаторы, думая, что могу предоставить свой собственный «словарь» (т. Е. Набор S), но я не мог понять, возможно ли это вообще.