/usr/lib/python2.7/dist-packages/fte/dfa.py is in python-fte 0.1.0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import fte.cDFA
class LanguageIsEmptySetException(Exception):
"""Raised when the input language results in a set that is not rankable.
"""
pass
class IntegerOutOfRangeException(Exception):
pass
class InvalidRegexParametersException(Exception):
pass
class DFA(object):
def __init__(self, cDFA, fixed_slice):
self._cDFA = cDFA
self.fixed_slice = fixed_slice
self._words_in_language = self._cDFA.getNumWordsInLanguage(
0, self.fixed_slice)
self._words_in_slice = self._cDFA.getNumWordsInLanguage(
self.fixed_slice, self.fixed_slice)
self._offset = self._words_in_language - self._words_in_slice
if self._words_in_slice == 0:
raise LanguageIsEmptySetException()
self._capacity = int(math.floor(math.log(self._words_in_slice, 2))) - 1
def rank(self, X):
"""Given a string ``X`` return ``c``, where ``c`` is the lexicographical
rank of ``X`` in the language of all strings of length ``fixed_slice``
generated by ``regex``.
"""
retval = self._cDFA.rank(X)
return retval
def unrank(self, c):
"""The inverse of ``rank``.
"""
retval = self._cDFA.unrank(c)
return retval
def getCapacity(self):
"""Returns the size, in bits, of the language of our input ``regex``.
Calculated as the floor of log (base 2) of the cardinality of the set of
strings up to length ``fixed_slice`` in the language generated by the input
``regex``.
"""
return self._capacity
def getNumWordsInSlice(self, n):
"""Returns the number of words in the language of length ``n``"""
return self._cDFA.getNumWordsInLanguage(n, n)
|