故事尾音

概率图模型

Hexo Next 主题优化

记录一些 Hexo Next 博客优化的文章：

• 代码块优化
• 设置圆形头像并旋转
• hexo 数学公式
• hexo 中插入视频音频
• 主题个性化配置
• hexo 背景修改
• hexo gitment 配置

本文主要是对网上的一些文章的总结，参考的文章在文末已经列出

音频信号是模拟信号，我们需要将其保存为数字信号，才能对语音进行算法操作，WAV 是 Microsoft 开发的一种声音文件格式，通常被用来保存未压缩的声音数据。

语音信号有三个重要的参数：声道数、取样频率和量化位数。

• 声道数：可以是单声道或者是双声道
• 采样频率：一秒内对声音信号的采集次数，44100Hz 采样频率意味着每秒钟信号被分解成 44100 份，如果采样率高，那么媒体播放音频时会感觉信号是连续的。
• 量化位数：用多少 bit 表达一次采样所采集的数据，通常有 8bit、16bit、24bit 和 32bit 等几种

如果你需要自己录制和编辑声音文件，推荐使用 Audacity (http://audacity.sourceforge.net)， 它是一款开源的、跨平台、多声道的录音编辑软件。

从青蛙跳台阶说起

这个问题和斐波纳契数字问题是一样的。题目描述如下：

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

考虑递归

首先用递归的思路来考虑。递归是倒着分析的。

假如只差一步就能走完整个台阶，要分为几种情况？因为每一步能走一级或者两级台阶，所以有如下两种情况：

• 最后一步走 2 级台阶，也就是从 n-2 级到 n 级
• 最后一步走 1 级台阶，也就是从 n-1 级到 n 级

所以第 n 步的走法由两种方法的和构成。如果定义 F (n) 为第 n 步的走法，那么 F (n)=F (n-1)+F (n-2)。这个公式称之为递推公式。
当只有 1 级台阶和 2 级台阶时走法很明显，即 F (1)=1、F (2)=2。称之为边界条件。
两部分具备之后，很容易可以写出代码：

1
2
3
4
5
6

def fun(n):
    if n==2:
        return 2
    if n==1:
        return 1
    return fun(n-1)+fun(n-2)

重叠子问题

我们不妨把上面的递归式子以树的形式表示出来，结果如下：

1
2
3
4
5
6
7
8
9

                       F(5)
                  /             \
             F(4)                  F(3)
          /      \                /     \
      F(3)       F(2)         F(2)     F(1)
     /     \     /    \       /    \
   F(2)   F(1) F(1)  F(0)  F(1)   F(0)
  /    \
F(1)  F(0)

记忆化搜索

记忆化搜索的思路如下：每当我们需要解决子问题时，我们首先查找查找表。如果预先计算的值存在，那么我们返回该值，否则我们计算值，并将结果放在查找表中，以便以后可以重复使用。

1
2
3
4
5
6
7
8

lookup = [0,1,2]+[0]*100

def fun(n):

    if lookup[n] == 0:
        lookup[n] = fun(n-1)+fun(n-2)

    return lookup[n]

LRU 缓存

LRU（Least recently used，最近最少使用），其核心思想是 “如果数据最近被访问过，那么将来被访问的几率也更高”。对于本题目，如果是高频出现的计算函数的结果会被放到缓存中，再次出现只需要在缓存中读取即可，和记忆化搜索类似。python 有 LRU 的内置函数：

1
2
3
4
5
6
7
8

from functools import lru_cache
@lru_cache(None)
def fun(n):
    if n==2:
        return 2
    if n==1:
        return 1
    return fun(n-1)+fun(n-2)

有了上诉方法，n=100 已经可以计算了。但是虽然有这两个缓解的方法，但是仍存在问题。当 n=1000 的时候仍然会存在堆栈溢出的问题。

一维动态规划

上面的思考都是基于递归的，即自顶而下的计算方法。如果我们换个思路，自底而上呢？

其实和上面的记忆化搜索很像了。首选记录 n=1 的情况和 n=2 的情况，然后依次向上计算，每次计算都存表即可。

1
2
3
4
5
6
7
8
9
10
11

N = 10

dp  = [0]*(N+1)
dp[1] = 1
dp[2] = 2

def fun(n):
    for i in range(n+1):
        if i>2:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]    

这种方法存的表称之为 DP Table, 这种解决思路称之为动态规划。本题目的 DP Table 是一维的，所以称之为一维动态规划。

当然针对这个问题，对空间还可以进一步优化：

1
2
3
4
5
6
7
8
9

def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    pre,prepre = 2,1
    for i in range(n - 2):
         prepre, pre = pre, pre + prepre
    return pre

动态规划和递归

上面我们已经见到过了：递归采用的是 “由上而下” 的解题策略并带有可能的” 子问题 “重复调用，时间复杂度自然高，而且容易造成堆栈的溢出。

动态规划和分治

两者的区别在于：动态规划的下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

动态规划和贪心

贪心算法每走一步都是不可撤回的，而动态规划是在一个问题的多种策略中寻找最优策略，所以动态规划中前一种策略可能会被后一种策略推翻。

一维动态规划 Leetcode 题目

• Climbing Stairs
• Decode Ways
• Unique Binary Search Trees
• Maximum Subarray
• Maximum Product Subarray
• Best Time to Buy and Sell Stock

二维动态规划

• 方法一：常规解法，先排序 (时间复杂度为 O (N*logN))
• 方法二：利用快速排序原理 (时间复杂度 O (N*logK)
• 方法三：利用最小堆的原理 (时间复杂度为 O (N*logK))
• 方法四：计数排序，用空间换取时间的方法，不适合浮点数

具体参考 文章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import bisect

#查找指定区间中包含的元素个数
A = [1,2,2.5,3,3.5,4,5]
lindex = bisect.bisect_left(A,2.5)
rindex = bisect.bisect_right(A,3.5)
print(lindex, rindex, rindex-lindex)

#分数等级
def grade(score,breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect.bisect(breakpoints, score)
    return grades[i]

print([grade(score) for score in [33, 99, 77, 70, 89, 90, 100]])

#二分查找
def binary_search_bisect(lst, x):
    from bisect import bisect_left
    i = bisect_left(lst, x)
    if i != len(lst) and lst[i] == x:
        return i
    return None

print(binary_search_bisect(A,4))

哈希函数

哈希函数又叫散列函数，输入范围很大，输出范围固定。
哈希函数的性质：

• 无限的输入域
• 输出值相同时，返回值一样
• 输入值不同时，返回值可能一样，也可能不一样
• 不同的输入值得到的 hash, 整体均匀分布在输出域上

1~3 是哈希函数的基础，第四点是评价 hash 函数优劣的关键。

场景

海量高维数据查找与某个数据最相似的一个或者多个数据。与其它基于 Tree 的数据结构，诸如 KD-Tree、SR-Tree 相比，它较好地克服了 Curse of Dimension，能够将 KNN 的时间复杂度缩减到 sub-linear。LSH 多被用于文本、多媒体（图像、音频）的相似性判断。