Regular Expression (regex)

• Regular expression可以用於尋找或確認特定格式的資料，例如確認驗證電話號碼或email是否符合格式。

  import re
  text = "My number is 0911111111. I am avaliable from 8am to 5pm."
  
  patt = "from"
  
  print(re.search(patt, text))
  # <re.Match object; span=(40, 44), match='from'>
  
  match = re.search(patt, text)
  print(match.group()) # from (得到的結果為何
  print(match.span()) # (40, 44) (找到的位置
  print(match.start()) # 40
  print(match.end()) # 44
  

  re.search 只會找到第一個符合的即停止，想找全部的話可以用re.findall 其會return一個list。

  import re
  text = "from, My number is 0911111111. I am avaliable from 8am to 5pm, from"
  
  patt = "from"
  
  match = re.search(patt, text)
  print(match.group()) # from
  print(match.span()) # (0, 4)
  print(match.start()) # 0
  print(match.end()) # 4
  
  match = re.findall(patt, text)
  print(match) # ['from', 'from', 'from']
  

• regular expression syntax

  regex大多都用raw string print(r”...”)來寫，可以避免有特殊意義的字或符號。

  • [ ] 或[ - ] 用於表示characters的集合。
  • . 可以match所有的character。
  • Kleene star * 可以接受任何數量的指定character
  • +與 * 代表意義相近，差異為使用+的話至少要有一個指定的character
  • \\d 可以match 0-9，找到所有十進位的數字。\\D 與\\d相反，找到所有非十進位數字的字符。
  • { }，如{m}, {m,n}, {m,}，設定數量
  • \\w可以找到所有英文字母及數字。\\W會找到所有不是英文字母及數字的字符，如?, +, -。
  • \\s會match空白鍵，\\S會match任何非空白鍵的部分。
  • 使用r”\\.”即可輸出 .
  • \\b match empty string
  • | 代表”或”

• 可以使用( )表達一個group，並在return時會得到一個tuple，可以藉由此方法與tuple unpacking將目標部分找出。

  import re
  
  text = "My phone number is 808-744-0000, and 64-514-0000"
  
  print(re.findall(r"(\\d{2,3})-(\\d{3})-(\\d{4})", text))
  # [('808', '744', '0000'), ('64', '514', '0000')]
  
  result = re.findall(r"(\\d{2,3})-(\\d{3})-(\\d{4})", text)
  
  for areacode, other1, other2 in result:
      if areacode == "808":
          print("We found a number from Hawaii.")
  # We found a number from Hawaii.
  

Zip and Unzip

• 使用python來將檔案或資料夾壓縮的話，可以做到無失真壓縮，讓所有資料經過壓縮再解壓縮後仍可還原。

  import zipfile
  
  # 壓縮檔案
  zipped_file = zipfile.ZipFile("re.zip", "w")
  zipped_file.write("re.txt", compress_type=zipfile.ZIP_DEFLATED)
  zipped_file.write("re2.txt", compress_type=zipfile.ZIP_DEFLATED)
  zipped_file.close()
  
  # 解壓縮
  zipped_obj = zipfile.ZipFile("re.zip", "r")
  zipped_obj.extractall("result")
  zipped_obj.close()
  
  

• 使用shutil module中的make_archive() 可以將多個檔案或整個資料夾等直接進行壓縮。解壓縮可以使用unpack_archive()

  import shutil
  folder_we_want_to_zip = "c:\\\\Users\\\\USER\\\\Desktop\\\\...\\\\python codes\\\\Employee"
  output_name = "c:\\\\Users\\\\USER\\\\Desktop\\\\...\\\\python codes\\\\output"
  
  shutil.make_archive(output_name, "zip", folder_we_want_to_zip)
  
  sth_we_want_to_unzip = "c:\\\\Users\\\\USER\\\\Desktop\\\\...\\\\python codes\\\\output.zip"
  unzipped_folder_name = "c:\\\\Users\\\\USER\\\\Desktop\\\\new_folder"
  
  shutil.unpack_archive(sth_we_want_to_unzip, unzipped_folder_name, "zip")
  

Computational theory (Bonus)

Regular Expression

• Regular Expression由以下三個規則來定義：
  1. A set of letters Σ，可以被做成regex。null word Λ 也是一個regex。
  2. 如果r1與r2都是regex，則以下情況也都是regex：
     1. (r1)
     2. r1r2
     3. r1+r2
     4. r1* (代表任何數量的r1，此處*為Kleene star
  3. 除了以上，其他都不是regex
• Examples

  1. supposed Σ= {a, b}, and L is defined by a regex (a+b)(a+b)(a+b), then

     𝐿={𝑎𝑎𝑎, 𝑎𝑎𝑏, 𝑎𝑏𝑎, 𝑎𝑏𝑏, 𝑏𝑎𝑎, 𝑏𝑎𝑏, 𝑏𝑏𝑎, 𝑏𝑏𝑏}

  2. supposed Σ= {a, b}, and L is defined by a regex (a+b)a(a+b), then

     𝐿={𝑎, 𝑎𝑎, 𝑎𝑎𝑎, 𝑏𝑎𝑏, 𝑎𝑏𝑎𝑎𝑏, 𝑏𝑎𝑎𝑎𝑏𝑎, …}

Finite Automata

• Also called “finite-state machine”.

• 是一種抽象的數學計算模型。其一定要有一個起點，並且從一個state轉換到另一個state的過程即稱為transition。

• Kleene’s Theorem證明finite automata、regular expression與transition graph是等價的，三者可以互換。

• Finite automata有以下幾條規則：

  1. 標示負號的節點代表start state。
  2. 標示正號的節點代表end state。
  3. FA的起點只能有一個，但終點可以有無數個 (0到任意數都可以)。
  4. 每個state都需要有一個a和一個b由此state指出。

• Examples

  

Turing Machine

• Turing machine有一個input tape，tape上可能會有字，一字一格，沒有字的地方即為Λ。此外，會有一個tape head指向tape上的某處，當tape head指向某個字時，則可以讀取及修改這個字。

• Example