图 书 馆
稀疏傅里叶变换方法进行子串/模式匹配Sub-string/Pattern Matching in Sub-linear Time Using a Sparse Fourier Transform Approach |
|
| 课程网址: | https://videolectures.net/videos/kdd2017_janakiraman_transform_ap... |
| 主讲教师: | Nagaraj T. Janakiraman |
| 开课单位: | KDD 2017研讨会 |
| 开课时间: | 2017-12-01 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We consider the problem of querying a string (or, a database) of length N bits to determine all the locations where a substring (query) of length M appears either exactly or is within a Hamming distance of K from the query. We assume that sketches of the original signal can be computed offline and stored. Using a sparse Fourier transform computation based approach, we show that all such matches can be determined with high probability in sub-linear time. |
| 关 键 词: | 稀疏傅里叶; 亚线性时间; 子串模式匹配 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2024-11-27：liyq |
| 最后编审: | 2024-11-27：liyq |
| 阅读次数: | 2 |