问题：
考虑以下数据压缩技术。我们有一个包含m个文本字符串的表，每个字符串长度最多为k。我们想使用尽可能少的文本字符串来编码长度为n的数据字符串D。例如，如果我们的表包含（a，ba，abab，b），并且数据字符串是bababbaababa，则最佳编码方式是（b，abab，ba，abab，a）-总共五个代码单词。给出一种O（nmk）算法以找到最佳编码的长度。您可以假设每个字符串至少有一种在表中的编码。
我在skiena的“算法设计手册”书中发现了这个问题，并试图解决它。
我的最佳猜测是将字符串（D）的所有可能子字符串与长度为（m）的表中的所有文本进行匹配，时间复杂度：O（n * n * k * m）。
是否有更好的方法以O（nmk）伪多项式时间来解决这个问题？
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
const char* alphabet = "abcdef";
const int alphabetLen = strlen(alphabet);
void printTable(char** table, int k){
printf("Table: {%s", table[0]);
for(int i=1; i<k; i++){
printf(", %s", table[i]);
}
printf("}\n");
}
char** generateTable(int k, int m){
char** table = (char**)malloc(sizeof(char*)*k);
for(int i=0; i<k; i++){
int tableStringLen = (rand() % (m-1)) + 1;
table[i] = (char*)malloc(tableStringLen+1);
for(int j=0; j<tableStringLen; j++){
table[i][j] = alphabet[rand() % alphabetLen];
}
table[i][tableStringLen] = 0;
}
return table;
}
// Unfortunately, the length of the string is partially determined by the size of m
// it's done this way to avoid generating a random string and ensuring the table can encode it
char* generateString(char** table, int k, int m){
int minLength = rand()%200 + m*2;
char* string = (char*)malloc(minLength + m);
int j = 0;
for(int i=0; j<minLength; i++){
int tableStringIndex = rand() % k;
strcpy(string+j, table[tableStringIndex]);
j += strlen(table[tableStringIndex]);
}
string[j] = 0;
return string;
}
void printSolution(char* string, int* branchLengths, int n){
if(!n){ return; }
printSolution(string, branchLengths, branchLengths[n]);
printf("%.*s ", n-branchLengths[n], string+branchLengths[n]);
}
int* solve(char* string, char** table, int n, int m, int k, int* comparisons){
int* currentBranchEnds = (int*)calloc(sizeof(int), n); // keeps track of all of the current ends
int currentBranchCount = 1; // keeps track of how many active branch ends there are
int* newBranchEnds = (int*)calloc(sizeof(int), n); // keeps track of the new branches on each iteration
int newBranchCount = 0;
int* branchLengths = (int*)calloc(sizeof(int), (n+1)); // used to reconstruct the solution in the end
// used for O(1) length lookups
int* tableStringLengths = (int*)malloc(sizeof(int) * k);
for(int i=0; i<k; i++){ tableStringLengths[i] = strlen(table[i]); }
*comparisons = 0;
// continue searching while the entire string hasn't been encoded
while(!branchLengths[n]){
// for every active branch
for(int i=0; i<currentBranchCount; i++){
// try all table strings
for(int j=0; j<k; j++){
int newBranchEnd = currentBranchEnds[i] + tableStringLengths[j];
// if the new length (branch end) already exists OR
// if the new branch would be too long for the string, discard the branch
*comparisons += 1;
if(newBranchEnd > n || branchLengths[newBranchEnd]){ continue; }
// check to see if the table string matches the target string at this position
// could be done with strcmp, but is done in a loop here to be explicit about complexity
char match = 1;
for(int l=0; table[j][l]; l++){
*comparisons += 1;
if(string[currentBranchEnds[i] + l] != table[j][l]){
match = 0;
break;
}
}
// if it matches, we can create a new branch at this position
*comparisons += 1;
if(match){
branchLengths[newBranchEnd] = currentBranchEnds[i];
newBranchEnds[newBranchCount] = newBranchEnd;
newBranchCount += 1;
}
}
}
// swap the branch ends arrays to save copying
int* tmp = currentBranchEnds;
currentBranchEnds = newBranchEnds;
newBranchEnds = tmp;
currentBranchCount = newBranchCount;
newBranchCount = 0;
}
free(currentBranchEnds);
free(newBranchEnds);
free(tableStringLengths);
return branchLengths;
}
int main(){
int k = rand() % 30 + 2;
int m = rand() % 15 + 2;
char** table = generateTable(k, m);
printTable(table, k);
char* string = generateString(table, k, m);
int n = strlen(string);
printf("String: %s\n", string);
int comparisons;
int* solution = solve(string, table, n, m, k, &comparisons);
printf("Solution: ");
printSolution(string, solution, n);
printf("\n");
printf("Comparisons: %d\n", comparisons);
for(int i=0; i<k; i++){ free(table[i]); }
free(table);
free(solution);
free(string);
}
很明显，比较次数（计算出来的）与 n、m 和 k 的大小之间存在线性关系。这表明复杂度为 O(nmk)。words = {'ba', 'a', 'abab', 'b'}
sentence = 'bababbaababa'
def smallest_cut(sentence, words):
max_word_length = max(len(w) for w in words)
words_by_length = [[] for i in range(max_word_length + 1)]
for w in words:
words_by_length[len(w)].append(w)
results_by_length = dict()
results_by_length[0] = []
for i in range(len(sentence) + 1):
for j in range(max(0, i-max_word_length), i):
if j in results_by_length:
for w in words_by_length[i-j]:
if sentence[j:i] == w:
if i not in results_by_length or len(results_by_length[j]) + 1 < len(results_by_length[i]):
results_by_length[i] = results_by_length[j] + [w]
return results_by_length[len(sentence)]
print(smallest_cut(sentence, words))
第一个for循环执行了n次迭代，第二个和第三个循环共执行了m次迭代，比较sentence[j:i] == w需要k次操作。
w = sentence[j:i] 和检查 if w in words_by_length[i-j]:（后者应该是一个集合）来提高复杂性。 我认为那样的话应该是 O((n+m)k)。 - no commentk<=m（因为它们是由输入“定义”的，而不是由我们对其进行操作），但你是对的，现实切片的数量也受到 m 的限制。所以... O(nk min(m,k))? - no commentsolve(i) 计算前i个字母的结果，因此答案是 solve(n)。对于每个前缀长度 i，尝试所有单词作为该前缀的可能后缀。i 参数，每个检查m个单词，并且每个单词检查最多需要k个字母检查，所以时间复杂度为O(nmk)。
from functools import lru_cache
words = 'a', 'ba', 'abab', 'b'
sentence = 'bababbaababa'
@lru_cache
def solve(i):
return i and min((solve(i - len(word)) + 1
for word in words
if sentence.endswith(word, None, i)),
default=float('inf'))
print(solve(len(sentence)))
from collections import defaultdict
from typing import Set
def smallest_cut(sentence: str, words: Set[str]) -> int:
lookup = [1e10 for i in range(len(sentence)+1)]
step_results = defaultdict(set)
step_results[0].add(sentence)
curr_step = 1
while step_results[curr_step-1]: # this line and next line has in fact O(n) because of 'lookup'
for curr_sentence in step_results[curr_step-1]: # look to comment above
for word in words: # O(m)
if curr_sentence.startswith(word): # O(k)
new_sentence = curr_sentence[len(word):] # remove prefix
if new_sentence:
if lookup[len(new_sentence)] > curr_step:
lookup[len(new_sentence)] = curr_step # cheat with lookup for O(1) complexity instead O(log(n))
step_results[curr_step].add(new_sentence)
else: # we found shotrest encoding
return curr_step
curr_step += 1
smallest_cut('bababbaababa', {'ba', 'a', 'abab', 'b'})
while 和另一个行的复杂度为 O(n)，因为 steps_results 将保存最大 n 个句子，因为 lookup 的技巧确保了它。 - questerprint(smallest_cut('bababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbbababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbaabababababbbababbaabababababbaabababababbaabababababbaabababababbaababababab', {'a', 'b', 'abab', 'ba'})) 216 - quester