所有由yl发布的文章

过去的一年，简单回顾，短视频吞噬了太多的时间。开发这一技术的人太了解人性的弱点了，拇指的上滑有无穷的魔力，不断刺激大脑中的兴奋区，让人欲罢不能。我自认为还是一个有自控力的人，“就放松一下”，“就看一个小时”…，很遗憾，没有胜出过。有时候工作确实累了，想通过小视频来放松一下，而实际情况是，看完之后有深深的自责感，看了很多，发现有收获的不多。而且惊奇地发现，最近看的内容和一年前的完全不一样啊，难道是一年前的博主不更新了？我还特地去搜了下，发现都还在，只是“算法”不给我推荐了。那我岂不是被控的小鼠？

趁着新的一年到来，趁着这个契机，立下一个新年flag–远离短视频。那省下的时间干吗？看paper，看教学视频，读书，学语言。初试了几天，突然发现时间变多了，学习了很久，抬头看钟，发现未到11点，有点豁然开朗的感觉。短视频倾向于短平快的内容，像一些艰深的、系统的、综合的知识，是需要很长的静下来的时间来学习的，而恰恰是这些知识，才是我们个人能力、谈吐、学识的来源。

一星期纪念，感觉很轻松，一点难受的感觉都没有，加油，坚持！

随笔

重启

2025年1月3日 yl

好久没有写东西，网站都有点落灰了！

看看之前写的东西，当时觉得有点微不足道的东西，现在读起来也有些许新意。记述心路历程，留下成长足迹。

不管怎样，动手写起来！

TTS

HiFi-GAN解读

2025年1月3日 yl

HiFi-GAN: Generative Adversarial Networks for
Efficient and High Fidelity Speech Synthesis

目前vcoder的三个主流方向：

Autoregressive。代表：wavenet。缺点：生成语音效率低
Flow-based。代表：Parallel Wavenet、 waveglow。缺点：参数量大。
GAN-based。代表：MelGAN、CLariNet、GAN-TTS。缺点：生成语音音质稍差。

HiFi-GAN的优势：合成速度快、泛化能力强、参数量小、合成音质高。

算法刷题

最长回文子串

2020年6月14日 yl

这是算法的第5题，描述如下：

给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000.

示例1：

输入：”babad”

输出：”bab”

注意：”aba”也是一个有效答案。

示例2：

输入：”cbbd”

输出：”bb”

此题难度：中等，通过率30%过一点。

题解转自官方解法，链接如下：

转自：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

方法一：动态规划

思路与算法

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道

“bab” 是回文串，那么“ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。

根据这样的思路，我们就可以用动态规划的方法解决本题。我们用P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串（下文表示成 s[i:j]）是否为回文串：
P(i,j) = true if 如果子串 Si…Sj 是回文串;

P(i,j) = false 其他情况。

这里的「其它情况」包含两种可能性：
s[i,j] 本身不是一个回文串；
i>j，此时 s[i,j] 本身不合法。

那么我们就可以写出动态规划的状态转移方程：
P(i,j)=P(i+1,j−1)∧(S_i == S_j)

也就是说，只有 s[i+1:j−1] 是回文串，并且s 的第i 和 j个字母相同时，s[i:j] 才会是回文串。

上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

P(i,i)=true

P(i,i+1)=(Si==Si+1)

根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 P(i,j)=true 中 j−i+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

复杂度分析

时间复杂度：
O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。

空间复杂度：
O(n^2)，即存储动态规划状态需要的空间。

方法2：中心扩展算法

思路与算法

我们仔细观察一下方法一中的状态转移方程：

P(i,j) = true;

P(i, i+1) = (S_i == S_i+1);

P(i,j)=P(i+1,j−1)∧(S_i == S_j)

出其中的状态转移链：
P(i,j)←P(i+1,j−1)←P(i+2,j−2)←⋯←某一边界情况

可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从 P(i+1,j−1) 扩展到 P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。

聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。

复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次。

空间复杂度：O(1)。

代码如下（将两个题解放在一个文件里，分别为_s1和_s2):

def longestPalindrome_s1(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    ans = ""
    for l in range(n):
        for i in range(n):
            j = i + l
            if j >= len(s):
                break
            if l == 0:
                dp[i][j] = True
            elif l == 1:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])
            if dp[i][j] and l + 1 > len(ans):
                ans = s[i:j+1]
    return ans


print(longestPalindrome_s1("fsafsdabbad"))

########################################################################

def expandAroundCenter(s,left,right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1

def longestPalindrome_s2(s):
    start, end = 0, 0
    for i in range(len(s)):
        left1, right1 = expandAroundCenter(s, i, i)
        left2, right2 = expandAroundCenter(s, i, i+1)
        if right1 - left1 > end - start:
            start, end = left1, right1
        if right2 - left2 > end - start:
            start, end = left2, right2
    return s[start: end+1]

print(longestPalindrome_s2("fsafsdabbad"))

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

C++

函数调用在哪里？

2020年4月9日 yl

今天看到一段函数，如下：

std::string comm_done_filename(const std::string & base_done_filename, const int & job_id) {
    return base_done_filename + ".done." + IntToString(job_id);
}

std::string comm_avg_model_name(const std::string & base_model_filename, const int &count) {
    return base_model_filename + ".avg." + IntToString(count);
}

隐约觉得可以用宏来解决, 因为函数名中的“done” 和“avg”，与返回值中包含的是相同的，而且两个函数形式完全一样，没有必要写成两个函数。

代码如下：

#define BT(name,flags,base,count) \
    std::string comm_##flags##_##name (const std::string & base,const int & count) { \
    return base + "."+ #flags + "." + IntToString(count); \
}

BT(model_name,avg,kaka,akak)
BT(filename,done,kaka,akak)

注意：函数名中的flags前后要有两个##, 而name只有前面有##，因为name之后没有东西了。

声名中kaka, akak是没有什么意义的，起个形参的作用。

调用的时候，当然可以直接用函数名：comm_done_filename,comm_avg_model_name。

另外，也可以使用函数指针数组或者用map。

首先，定义一个函数指针：

typedef std::string (*TransFun)(const std::string &, const int &);

函数指针数组如下：

 TransFun fun[] = {comm_done_filename,comm_avg_model_name};

map如下：

 map<string,TransFun> FunStrMap;

调用的时候当然是看不到函数名的：

 string aa = FunStrMap["done"]("cheng",3);
 string AA = fun[0]("cheng",3);

不多说，整个代码如下：

#include <iostream>
#include <string>
#include <sstream>
#include <map>

using namespace std;

std::string IntToString(const int &i) {
    std::stringstream ss;
    ss << i;
    return ss.str();
}
#define BT(name,flags,base,count) \
    std::string comm_##flags##_##name (const std::string & base,const int & count) { \
    return base + "."+ #flags + "." + IntToString(count); \
}

BT(model_name,avg,kaka,akak)
BT(filename,done,kaka,akak)

/*
std::string comm_done_filename(const std::string & base_done_filename, const int & job_id) {
    return base_done_filename + ".done." + IntToString(job_id);
}

std::string comm_avg_model_name(const std::string & base_model_filename, const int &count) {
    return base_model_filename + ".avg." + IntToString(count);
}
*/
typedef std::string (*TransFun)(const std::string &, const int &);
int main(){

    TransFun fun[] = {comm_done_filename,comm_avg_model_name};
    map<string,TransFun> FunStrMap;
    FunStrMap["done"] = fun[0];
    //FunStrMap["avg"] = fun[1];
    FunStrMap.insert(pair<string,TransFun>("avg",fun[1]));//不同添加元素的方法
    string aa = FunStrMap["done"]("cheng",3);
    string AA = fun[0]("cheng",3);
    string bb = FunStrMap["avg"]("yu",8);
    string BB = fun[1]("yu",8);
    cout<<aa<<"\n"<<bb<<endl;
    cout<<AA<<"\n"<<BB<<endl;
    return 0;

}

输出结果：

cheng.done.3
yu.avg.8
cheng.done.3
yu.avg.8

总结一下知识点：

宏定义，函数指针，函数指针数组、map

IT&Linux

cygwin命令变慢

2020年3月17日 yl

如果发现cygwin启动慢了，连ls都变得无法忍受了，别怀疑，关掉QQ电脑管家就是了！

C++

C++–将基础类型转成string类型

2020年3月9日 yl

 template <typename T>
 std::string ToString(const T& t) {
    std::ostringstream os;
    os << t;
    return os.str();
 }

ASR

CTC的理解

2020年3月2日 yl

CTC技术近些年搭着End2End的顺风火了起来，查了一下原文，竟然是出在2006 Pittsburgh “International Conference on Machine Learning”的会议文章。Paper很容易找，搜索一下，能找到很多可用链接。

还是郑重地给出这篇文章的名字：

Connectionist Temporal Classification: Labelling Unsegmented
Sequence Data with Recurrent Neural Networks

要想理解这篇文章，要解决几个问题：

1. 如何实现了end2end？

2. 损失函数有什么特别？

3. 前后向算法在这个算法中的作用是什么？

其实理解这篇文章之后，这三个问题的本质是一样。

第一个问题：CTC如何实现了end2end?

在ASR领域，像DNN,LSTM这样的深度模型，输出的CD-phone的state。要做后面的文字的输出，需要加入字典（Lex）、语言模型（LM），与声学模型（AM）构成解码图后才可以。CTC越过字典与语言模型，直接输出phone或者字母（英文）、字（中文），虽然在性能上达不到其他的非e2e的模型的识别率，但这肯定是未来的大趋势，毕竟技术的发展应该是越来越简单，越来越直接。而且在实现的工程上，CTC在做识别时，也会结合LM，效果会更好。

与传统的声学模型训练相比，采用CTC作为损失函数的声学模型训练，是一种完全端到端的声学模型训练，不需要预先对数据做对齐，只需要一个输入序列和一个输出序列即可以训练。这样就不需要对数据对齐和一一标注，并且CTC直接输出序列预测的概率，不需要外部的后处理。

对于一个200帧的音频数据，假设真实的输出是7。经过神经网络后（可以dnn，rnn，lstm等），出来的序列还是200。比如说“chengyu”,将chengyu扩展到200的长度，路径有许多种。扩展的原则是：将一个字符扩展成连续多个，所有字符的长度总和为200，所有以下这几种都是合理的：

ccccc…hhhh…eeeeeee…ngyu

chengyyyyyyyyyy….uuuuuuuu

这时有一个问题，那就是像hello中有两个l，怎样处理？方法是在两个l之间插入一个无意义的 $\epsilon$ ，例如hh…e…lllll $\epsilon$ lll…o..。

RNN模型本质是对 P(z|x) 建模，其中s表示输入序列，o表示输出序列，z表示最终的label，o和l存在多对一的映射关系，即：P(z│x)=∑P(o|x)，其中o是所有映射到z的输出序列。因此，只需要穷举出所有的o，累加一起即可得到P(z│x)，从而使得RNN模型对最终的label进行建模。

第二个问题：CTC的损失函数有什么特别？

不同于用于分类的cross entropy准则和回归的MSE准则，CTC的损失函数巧妙在设计为-logP(z│x)。使P(z│x)的最大，等价于损失最小，通过求log的负值，转化成一个求最小值问题。

3. 前后算法在这个算法中的作用是什么？

要想计算出每一条可能路径的得分再将所有这些得分加起来，用蛮力方式显然是不可能，巧妙地运用语音识别中的前后向算法，即baum-welch算法可以大大减少计算量，用动态规划的算法思想有效在提高了效率。

橙语

所有由yl发布的文章

坚持一个季度

坚持一个月

新年flag

重启