mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
100 lines
2.9 KiB
Python
100 lines
2.9 KiB
Python
"""
|
|
Move-to-front transform.
|
|
|
|
The move-to-front transform encodes each symbol as its current index in an
|
|
ordered alphabet, then moves that symbol to the front of the alphabet.
|
|
It is commonly used after the Burrows-Wheeler transform in lossless
|
|
compression pipelines.
|
|
|
|
Reference: https://en.wikipedia.org/wiki/Move-to-front_transform
|
|
"""
|
|
|
|
|
|
def _validated_alphabet(alphabet: str) -> list[str]:
|
|
"""
|
|
Return a mutable alphabet list after validating uniqueness.
|
|
|
|
>>> _validated_alphabet("abc")
|
|
['a', 'b', 'c']
|
|
>>> _validated_alphabet("aba")
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: alphabet must contain unique characters
|
|
"""
|
|
if not isinstance(alphabet, str):
|
|
raise TypeError("alphabet must be a string")
|
|
if len(set(alphabet)) != len(alphabet):
|
|
raise ValueError("alphabet must contain unique characters")
|
|
return list(alphabet)
|
|
|
|
|
|
def move_to_front_encode(text: str, alphabet: str) -> list[int]:
|
|
"""
|
|
Encode text using the move-to-front transform.
|
|
|
|
>>> move_to_front_encode("banana", "abcdefghijklmnopqrstuvwxyz")
|
|
[1, 1, 13, 1, 1, 1]
|
|
>>> move_to_front_encode("banana", "abn")
|
|
[1, 1, 2, 1, 1, 1]
|
|
>>> move_to_front_encode("", "abc")
|
|
[]
|
|
>>> move_to_front_encode("bad", "abc")
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: character 'd' is not in the alphabet
|
|
"""
|
|
if not isinstance(text, str):
|
|
raise TypeError("text must be a string")
|
|
|
|
symbols = _validated_alphabet(alphabet)
|
|
encoded_text: list[int] = []
|
|
|
|
for char in text:
|
|
try:
|
|
char_index = symbols.index(char)
|
|
except ValueError:
|
|
message = f"character {char!r} is not in the alphabet"
|
|
raise ValueError(message) from None
|
|
encoded_text.append(char_index)
|
|
symbols.insert(0, symbols.pop(char_index))
|
|
|
|
return encoded_text
|
|
|
|
|
|
def move_to_front_decode(encoded_text: list[int], alphabet: str) -> str:
|
|
"""
|
|
Decode a move-to-front encoded list of indexes.
|
|
|
|
>>> move_to_front_decode([1, 1, 13, 1, 1, 1], "abcdefghijklmnopqrstuvwxyz")
|
|
'banana'
|
|
>>> move_to_front_decode([1, 1, 2, 1, 1, 1], "abn")
|
|
'banana'
|
|
>>> move_to_front_decode([], "abc")
|
|
''
|
|
>>> move_to_front_decode([3], "abc")
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: index 3 is not valid for alphabet size 3
|
|
>>> move_to_front_decode([-1], "abc")
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: index -1 is not valid for alphabet size 3
|
|
"""
|
|
symbols = _validated_alphabet(alphabet)
|
|
decoded_text = []
|
|
|
|
for index in encoded_text:
|
|
if not 0 <= index < len(symbols):
|
|
message = f"index {index} is not valid for alphabet size {len(symbols)}"
|
|
raise ValueError(message)
|
|
decoded_text.append(symbols[index])
|
|
symbols.insert(0, symbols.pop(index))
|
|
|
|
return "".join(decoded_text)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import doctest
|
|
|
|
doctest.testmod()
|