# BWT 程式碼片段解釋
### fmindex.py
#### 1. FMSimpleIndex._occ():
```python=
def _occ(self, qc):
""" get the first occurance of letter qc in left-column"""
occ = 0
#-------Your code should start here---------
occ = self.occ.get(qc)
#--------Your code should end here----------
return occ
```
程式碼解說：
```
line 1: 表示 _occ function 接收一參數 qc。
line 3: 先將 occ 歸零。
line 6: 利用 self.occ.get() 取得 qc 的 occurance value。
其中，self.occ 是由 bwt.calc_first_occ(self.data) 計算出。
self.occ 是 dictionary 型態，
因此透過 .get() 內建函示即可取得 qc 的 occ value。
line 8: 回傳 occ 值。
```
-----
#### 2. FMSimpleIndex._count():
```python=
def _count(self, idx, qc):
""" count the occurances of letter qc
(rank of qc) upto position idx """
if not qc in self.occ.keys(): return 0
count = 0
#-------Your code should start here---------
count = self.data[:idx].count(qc)
#--------Your code should end here----------
return count
```
程式碼解說：
```
line 1: 表示 _count function 接收兩參數 idx 與 qc。
line 5: 先檢查 qc 是否存在 occ dictionary 清單內，
若無，則 return 0。結束 _count()
line 9: 計算 count 值
self.data[:idx]: 將字串 transformedBWT 進行修剪。
讓字串只取到 idx 位置，後面接刪除。
接著使用 python 內建函示 .count() 計算剩餘字串中，有幾個 qc。
line 11: 回傳 count 值。
```
-----
#### 3. FMSimpleIndex._lf():
```python=
def _lf(self, idx, qc):
#-------Your code should start here---------
""" return the nearset lf mapping for letter qc at position idx """
lf_result = self._occ(qc) + self._count(idx, qc)
return lf_result
#--------Your code should end here----------
```
程式碼解說：
```
line 1: 表示 _lf function 接收兩參數 idx 與 qc。
line 5: 計算 lf 值。計算方法為呼叫兩 fmindex.py 內建函示 _occ() 與 _count()
分別計算出 occ 值與 count 值後，加總，即為 lf 值。
line 6: 回傳 lf 值。
```
-----
#### 4. FMSimpleIndex._bounds():
```python=
def bounds(self, q):
""" find the first and last suffix positions for query q """
"""These are positions in the BWT string"""
"""This is the meat of the FM search algorithm"""
top = 0
bot = len(self.data)
#-------Your code should start here---------
#iterate over letters in query string q in reverse
#reverse will change q, so use [::-1]
re_q = q[::-1]
for qc in re_q:
# calculate top (which maps the position
# in the last column to the position in the first column)
top = self._lf(top, qc)
# calculate bottom
bot = self._lf(bot, qc)
#--------Your code should end here----------
if top == bot: return (-1,-1)
#since bottom is non-inclusive,
#top==bot implies that the string was not found.
return (top,bot)
```
程式碼解說：
```
line 1: 表示 bounds function 接收一參數 q。
line 5: 先將 top bound 設定為 0。
line 6: 再將 bottom bound 設定為 transformedBWT 長度。
line 11: 將 q，即欲尋找之字串，反轉。
line 13: 用 for 迴圈，逐一取出字元。
line 16: 透過 fmindex.py 內建函示 _lf 進行 top bound 夾擊，產生新 top bound。
line 17: 透過 fmindex.py 內建函示 _lf 進行 bottom bound 夾擊，產生新 bottom bound。
line 21: 若 top bound 與 bottom bound 相等，便回傳 (-1, -1)，亦即找不到字串。
line 22: 反之，若 top/bottom bound 不相等，則回傳 (top, bot)。
```
-----
### bwt.py
#### 5. BurrowsWheeler.transform()
```python=
def transform(self, s):
""" Simplest Burrows-Wheeler transform implementation,
O(n^2) respective to the length of the text. """
assert self.EOS not in s,
"Input string cannot contain null character (%s)" % self.EOS
# add end of text marker
# please note that although this code
# uses the null marker to mark the end of the string,
# i've replaced it with "$" just for the output
# to help you debug your code -BZ
s += self.EOS
bwtTransformedString=''
# s is the input string,
# with the end-of-string character added for you
#-------Your code should start here---------
# generate a list of rotated input strings
inputstring = s * 2
after_rotation = []
for i in range(0, len(s)):
do_rotation = inputstring[i:i+len(s)]
after_rotation.append(do_rotation)
# sort the table of rotations
sort_result = sorted(after_rotation)
# extract the last characters of each row
for line in sort_result:
result = line[-1]
'''convert the characters to a string,
and store them in the variable bwtTransformedString
'''
bwtTransformedString = bwtTransformedString + result
#--------Your code should end here----------
return bwtTransformedString
```
程式碼解說：
```
line 1: 表示 transform function 接收一參數 s。
line 4: 排除字串中有 null character。
line 12: 將 null character 塞到 s 最後面，當 end of the string。
line 13: 將 bwtTransformedString 設為空字串。
line 19: 為方便 rotation，字串位移，我們先將 s * 2。
line 20: 宣告 after_rotation 為空 list。
line 23: 透過 for 迴圈，搭配 python string slicing 功能，進行字串 rotation。
line 24: 將 rotation 結果，append 進 after_rotation list 中。
line 27: 使用 python 內建函式 sorted()，將 after_rotation 進行排序，
並將結果傳給 sort_result。
line 30: 使用 for 迴圈，將 sort_result list 逐一取出。
line 31: 將 line 30 取出之結果，透過 python string 操弄，取出最後一個字元，
並將結果傳給 result。
line 36: 將 line 31 結果逐一 append 到 bwtTransformedString 字串上。
line 40: 回傳 bwtTransformedString。
```
-----
#### 6. calc_checkpoints()
```python=
def calc_checkpoints(s, step):
#returns the list of checkpoints, seperated by distance "step", each of which is a dictionary of the
#number of occurences of each character up to that point (noninclusive) -BZ
""" count the number of letters for each step and
return list of the counts"""
A = {} # letter count
C = [] # checkpoints, a list of letter count dictionaries
#-------Your code should start here---------
for ckp_index, q in enumerate(s):
point = ckp_index % step
if point == 0:
C.append(A.copy())
if A.get(q):
A[q] = A[q] + 1
else:
A[q] = 1
#--------Your code should end here----------
return C
```
程式碼解說：
```
此函式之目的為加速 count 值之計算。
在 index () 挑選 FMCheckpointing() 才會啟用。
line 1: 表示 transform function 接收一參數 s。
line 6: 給定一空 dictionary，存放 letter count，該 dict 命名為 A。
line 7: 給定一空 list，存放，各 check point 當時的 letter count。
line 11: 利用 enumerate() 搭配 for 迴圈，將 string 逐一取出，並授與編號。
line 12: 計算 checkpoint 檢查條件。
line 13: 透過檢查條件 ，判斷是否為 checkpoint。
若 index number % step 之餘數為零則為 checkpoint。
line 14: 若為 checkpoint，則將當時的 letter count 狀態 A，存入 list C 中。
line 16: 若可在 letter count dictionary A 中，
尋找到 q 字元，則將 letter count + 1。
line 19: 若無法在 letter count dictionary A 中，尋找到 q 字元，
則表示該字元為第一次出現，該 letter count 值 = 1。
line 22: 回傳 C (各 checkpoint 的 letter count 狀態)。ｓ
```
-----
# -*- coding: utf-8 -*-
print("讓事情變不可能的，是「人」，不是「事」。")
Sign in with Wallet
Connect another wallet