119 lines
3.9 KiB
C++
119 lines
3.9 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <list>
|
|
#include <string>
|
|
#include <unordered_map>
|
|
#include <map>
|
|
#include <algorithm>
|
|
#include <queue>
|
|
#include <deque>
|
|
#include <cmath>
|
|
#include <stack>
|
|
#include <array>
|
|
|
|
/**
|
|
* @brief
|
|
*
|
|
* 景轩单膝跪地，捂着流血的胸口慌忙的回答，在下……遭仇家暗算，误入仙子清修之地，实属无意！
|
|
* ['景轩单膝跪地', '捂着流血的胸口慌忙的回答', '在下……遭仇家暗算', '误入仙子清修之地', '实属无意！']
|
|
*
|
|
* [
|
|
* {'value': '锦轩单膝跪地', 'start': np.float64(0.7999999999999987), 'end': np.float64(2.3)},
|
|
* {'value': '捂着流血的胸口', 'start': np.float64(2.3), 'end': np.float64(4.18)},
|
|
* {'value': '慌忙地回答', 'start': np.float64(4.18), 'end': np.float64(5.34)},
|
|
* {'value': '在下遭仇家暗算', 'start': np.float64(6.099999999999999), 'end': np.float64(8.24)},
|
|
* {'value': '误入仙子清修之地', 'start': np.float64(8.24), 'end': np.float64(10.3)},
|
|
* {'value': '实属无益', 'start': np.float64(10.3), 'end': np.float64(11.5)}
|
|
* ]
|
|
*
|
|
*
|
|
* 鯉魚家有頭小綠驢叫李屢屢. 綠鯉魚家有頭小紅驢叫呂里里
|
|
* 李余家有頭小綠綠叫李余余
|
|
*/
|
|
class ASRMappingText {
|
|
|
|
private:
|
|
struct Alignment {
|
|
std::string text;
|
|
double start_timestamp;
|
|
double end_timestamp;
|
|
Alignment(): text(), start_timestamp(0), end_timestamp(0) {}
|
|
Alignment(std::string v, double start, double end): text(v), start_timestamp(start), end_timestamp(end) {}
|
|
};
|
|
|
|
public:
|
|
static inline float sub_cost(char32_t a, char32_t r) {
|
|
return (a == r) ? 0.0f : 1.0f;
|
|
}
|
|
|
|
std::vector<int> map_text(std::u32string source_text, std::u32string asr_data) {
|
|
const int n = source_text.size();
|
|
const int m = asr_data.size();
|
|
|
|
std::vector<std::vector<float>> dp(n + 1, std::vector<float>(m + 1, 0));
|
|
|
|
// 0 diag, 1 up (del A), 2 left(ins R)
|
|
std::vector<std::vector<int>> bt(n + 1, std::vector<int>(m + 1, 0));
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
dp[i][0] = dp[i - 1][0] + 1;
|
|
bt[i][0] = 1;
|
|
}
|
|
|
|
for (int j = 1; j <= m; j++) {
|
|
dp[0][j] = dp[0][j - 1] + 1;
|
|
bt[0][j] = 2;
|
|
}
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
for (int j = 1; j <= m; j++) {
|
|
float c_diag = dp[i-1][j-1] + sub_cost(source_text[i - 1], asr_data[j - 1]);
|
|
float c_up = dp[i-1][j] + 1;
|
|
float c_left = dp[i][j - 1] + 1;
|
|
float best = c_diag;
|
|
int dir = 0;
|
|
if (c_up < best) {
|
|
best = c_up;
|
|
dir = 1;
|
|
}
|
|
if (c_left < best) {
|
|
best = c_left;
|
|
dir = 2;
|
|
}
|
|
dp[i][j] = best;
|
|
bt[i][j] = dir;
|
|
}
|
|
}
|
|
|
|
std::vector<int> mapA(n, INT_MAX);
|
|
int i = n, j = m;
|
|
while (i > 0 || j > 0) {
|
|
int dir = bt[i][j];
|
|
if (i > 0 && j > 0 && dir == 0) {
|
|
mapA[i-1] = j-1;
|
|
i--;
|
|
j--;
|
|
} else if (i > 0 && (j == 0 || dir == 1)) {
|
|
mapA[i-1] = INT_MAX;
|
|
i--;
|
|
} else {
|
|
j--;
|
|
}
|
|
}
|
|
|
|
return mapA;
|
|
}
|
|
};
|
|
|
|
int main(void) {
|
|
class ASRMappingText asr;
|
|
|
|
auto k = asr.map_text(U"捂着流血的胸口慌忙的回答", U"慌忙的回答");
|
|
std::cout << k.size() << std::endl;
|
|
for (int i = 0; i < k.size(); i++) {
|
|
std::cout << k[i] << std::endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|