import  pandas as pd
import pickle
import os
import joblib

class TrieNode(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}###字母字符
        self.data1={}###中文
        self.is_word = False###标识是否汉字


class Trie(object):

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word,word1):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        node = self.root
        for letter in word:
            child = node.data.get(letter)
            if not child:
                node.data[letter] = TrieNode()
            node = node.data[letter]
        node.is_word = True
        if word1 not in node.data1:
            node.data1[word1]=1
        else:
            node.data1[word1]+=1

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.root
        for letter in word:
            node = node.data.get(letter)
            if not node:
                return False
        return node.is_word

    def starts_with(self, prefix):
        """
        Returns if there is any word in the trie
        that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for letter in prefix:
            node = node.data.get(letter)
            if not node:
                return False
        return True

    def get_start(self, prefix):
        """
        Returns words started with prefix
        :param prefix:
        :return: words (list)
        """
        def _get_key(pre, pre_node):
            words_list = []
            if pre_node.is_word:
                words_list.append([pre,pre_node.data1])
            for x in pre_node.data.keys():
                words_list.extend(_get_key(pre + str(x), pre_node.data.get(x)))
            return words_list

        words = []
        if not self.starts_with(prefix):
            return words
        # if self.search(prefix):
        #     words.append(prefix)
        #     return words
        node = self.root
        for letter in prefix:
            node = node.data.get(letter)
        return _get_key(prefix, node)


    def find_result(self,string):
        result =self.get_start(string)
        result = sort_by_value(result[0][1])
        result.reverse()
        return result[0]
    
    
def sort_by_value(d):
    return sorted(d.items(), key=lambda k: k[1])  # k[1] 取到字典的值。



def build_tree(data,save_path):

    trie = Trie()
    for element in data.values:
        trie.insert(element[0], element[1])
    joblib.dump(trie, save_path)
    return

def load_tree(path):
    trie = joblib.load(path)
    return trie

if __name__ == '__main__':

    ###
    build_tree(data,save_path)
    ###
    tree=load_tree(save_path)
    print(tree.find_result("XXXXXXXX"))

import torch
from torch import nn
from torch.autograd import Variable
###random
embeds = nn.Embedding(2, 5) 
print(embeds.weight)
embeds = nn.Embedding(2, 5) 
print(embeds.weight)
###from pretrain
weight = torch.FloatTensor([[1, 2.3, 3], [4, 5.1, 6.3]])
embedding = nn.Embedding.from_pretrained(weight)
print(embedding.weight)

Parameter containing:
tensor([[-0.1754,  1.6604, -1.5025, -1.0980, -0.4718],
        [-1.1276,  0.1408, -1.0746, -1.2768, -0.6789]], requires_grad=True)
Parameter containing:
tensor([[-0.7366,  0.0607,  0.6151,  0.2282,  0.3878],
        [-1.1365,  0.1844, -1.1191, -0.8787, -0.5121]], requires_grad=True)
Parameter containing:
tensor([[1.0000, 2.3000, 3.0000],
        [4.0000, 5.1000, 6.3000]])

self.embedding = nn.Embedding.from_pretrained(config.embedding_pretrained, freeze=False)
self.embedding_ngram2 = nn.Embedding(config.n_gram_vocab, config.embed)
self.embedding_ngram3 = nn.Embedding(config.n_gram_vocab, config.embed)

def _lcs_table(source, target):
  """Returns the Longest Common Subsequence dynamic programming table."""
  rows = len(source)
  cols = len(target)
  lcs_table = [[0] * (cols + 1) for _ in range(rows + 1)]
  for i in range(1, rows + 1):
    for j in range(1, cols + 1):
      if source[i - 1] == target[j - 1]:
        lcs_table[i][j] = lcs_table[i - 1][j - 1] + 1
      else:
        lcs_table[i][j] = max(lcs_table[i - 1][j], lcs_table[i][j - 1])
  return lcs_table


def _backtrack(table, source, target, i, j):
  """Backtracks the Longest Common Subsequence table to reconstruct the LCS.

  Args:
    table: Precomputed LCS table.
    source: List of source tokens.
    target: List of target tokens.
    i: Current row index.
    j: Current column index.

  Returns:
    List of tokens corresponding to LCS.
  """
  if i == 0 or j == 0:
    return []
  if source[i - 1] == target[j - 1]:
    # Append the aligned token to output.
    return _backtrack(table, source, target, i - 1, j - 1) + [target[j - 1]]
  if table[i][j - 1] > table[i - 1][j]:
    return _backtrack(table, source, target, i, j - 1)
  else:
    return _backtrack(table, source, target, i - 1, j)

def _compute_lcs(source, target):
  # s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2} return 35778
  table = _lcs_table(source, target)
  return _backtrack(table, source, target, len(source), len(target))
  
  
  
def _get_added_phrases(source: Text, target: Text) -> Sequence[Text]:
    """
    Computes the phrases that need to be added to the source to get the target.
    """
    sep = ''
    source_tokens = utils.get_token_list(source.lower())
    target_tokens = utils.get_token_list(target.lower())
    #compute Longest Common Subsequence
    kept_tokens = _compute_lcs(source_tokens, target_tokens)
    added_phrases = []
    kept_idx = 0
    phrase = []
    for token in target_tokens:
        if kept_idx < len(kept_tokens) and token == kept_tokens[kept_idx]:
            kept_idx += 1
            if phrase:
                added_phrases.append(sep.join(phrase))
                phrase = []
        else:
            phrase.append(token)
    if phrase:
        added_phrases.append(sep.join(phrase))
    return added_phrases

Idx Frequency  Coverage (%)   Phrase
1  19 94.22  址
2  15 95.27  单位
3  8  95.76  地
4  6  96.17  执勤

KEEP
DELETE
KEEP|址
DELETE|址
KEEP|单位
DELETE|单位
KEEP|地
DELETE|地
KEEP|执勤
DELETE|执勤

def _compute_single_tag(
        self, source_token, target_token_idx,
        target_tokens):
    """Computes a single tag.

    The tag may match multiple target tokens (via tag.added_phrase) so we return
    the next unmatched target token.

    Args:
      source_token: The token to be tagged.
      target_token_idx: Index of the current target tag.
      target_tokens: List of all target tokens.

    Returns:
      A tuple with (1) the computed tag and (2) the next target_token_idx.
    """
    source_token = source_token.lower()
    target_token = target_tokens[target_token_idx].lower()
    if source_token == target_token:
        return tagging.Tag('KEEP'), target_token_idx + 1
    # source_token!=target_token
    added_phrase = ''
    for num_added_tokens in range(1, self._max_added_phrase_length + 1):
        if target_token not in self._token_vocabulary:
            break
        added_phrase += (' ' if added_phrase else '') + target_token
        next_target_token_idx = target_token_idx + num_added_tokens
        if next_target_token_idx >= len(target_tokens):
            break
        target_token = target_tokens[next_target_token_idx].lower()
        if (source_token == target_token and
                added_phrase in self._phrase_vocabulary):
            return tagging.Tag('KEEP|' + added_phrase), next_target_token_idx + 1
    return tagging.Tag('DELETE'), target_token_idx


def _compute_tags_fixed_order(self, source_tokens, target_tokens):
    """Computes tags when the order of sources is fixed.

    Args:
      source_tokens: List of source tokens.
      target_tokens: List of tokens to be obtained via edit operations.

    Returns:
      List of tagging.Tag objects. If the source couldn't be converted into the
      target via tagging, returns an empty list.
    """
    tags = [tagging.Tag('DELETE') for _ in source_tokens]
    # Indices of the tokens currently being processed.
    source_token_idx = 0
    target_token_idx = 0
    while target_token_idx < len(target_tokens):
        tags[source_token_idx], target_token_idx = self._compute_single_tag(
            source_tokens[source_token_idx], target_token_idx, target_tokens)
        ####################################################################################
        # If we're adding a phrase and the previous source token(s) were deleted,
        # we could add the phrase before a previously deleted token and still get
        # the same realized output. For example:
        #    [DELETE, DELETE, KEEP|"what is"]
        # and
        #    [DELETE|"what is", DELETE, KEEP]
        # Would yield the same realized output. Experimentally, we noticed that
        # the model works better / the learning task becomes easier when phrases
        # are always added before the first deleted token. Also note that in the
        # current implementation, this way of moving the added phrase backward is
        # the only way a DELETE tag can have an added phrase, so sequences like
        # [DELETE|"What", DELETE|"is"] will never be created.
        if tags[source_token_idx].added_phrase:
            # # the learning task becomes easier when phrases are always added before the first deleted token
            first_deletion_idx = self._find_first_deletion_idx(
                source_token_idx, tags)
            if first_deletion_idx != source_token_idx:
                tags[first_deletion_idx].added_phrase = (
                    tags[source_token_idx].added_phrase)
                tags[source_token_idx].added_phrase = ''
        ########################################################################################
        source_token_idx += 1
        if source_token_idx >= len(tags):
            break

    # If all target tokens have been consumed, we have found a conversion and
    # can return the tags. Note that if there are remaining source tokens, they
    # are already marked deleted when initializing the tag list.
    if target_token_idx >= len(target_tokens):  # all target tokens have been consumed
        return tags
    return []  # TODO

def _compute_tags_fixed_order(self, source_tokens, target_tokens):
    """Computes tags when the order of sources is fixed.

    Args:
      source_tokens: List of source tokens.
      target_tokens: List of tokens to be obtained via edit operations.

    Returns:
      List of tagging.Tag objects. If the source couldn't be converted into the
      target via tagging, returns an empty list.
    """
  

    tags = [tagging.Tag('DELETE') for _ in source_tokens]
    # Indices of the tokens currently being processed.
    source_token_idx = 0
    target_token_idx = 0
    while target_token_idx < len(target_tokens):
        tags[source_token_idx], target_token_idx = self._compute_single_tag(
            source_tokens[source_token_idx], target_token_idx, target_tokens)
        #########################################################################################
        # If we're adding a phrase and the previous source token(s) were deleted,
        # we could add the phrase before a previously deleted token and still get
        # the same realized output. For example:
        #    [DELETE, DELETE, KEEP|"what is"]
        # and
        #    [DELETE|"what is", DELETE, KEEP]
        # Would yield the same realized output. Experimentally, we noticed that
        # the model works better / the learning task becomes easier when phrases
        # are always added before the first deleted token. Also note that in the
        # current implementation, this way of moving the added phrase backward is
        # the only way a DELETE tag can have an added phrase, so sequences like
        # [DELETE|"What", DELETE|"is"] will never be created.
        if tags[source_token_idx].added_phrase:
            # # the learning task becomes easier when phrases are always added before the first deleted token
            first_deletion_idx = self._find_first_deletion_idx(
                source_token_idx, tags)
            if first_deletion_idx != source_token_idx:
                tags[first_deletion_idx].added_phrase = (
                    tags[source_token_idx].added_phrase)
                tags[source_token_idx].added_phrase = ''
        #######################################################################################

        source_token_idx += 1
        if source_token_idx >= len(tags):
            break

    # If all target tokens have been consumed, we have found a conversion and
    # can return the tags. Note that if there are remaining source tokens, they
    # are already marked deleted when initializing the tag list.
    if target_token_idx >= len(target_tokens):  # all target tokens have been consumed
        return tags
    ####fix bug by lavine

    ###strategy1
    added_phrase = "".join(target_tokens[target_token_idx:])
    if added_phrase in self._phrase_vocabulary:
        tags[-1] = tagging.Tag('DELETE|' + added_phrase)
        print(''.join(source_tokens))
        print(''.join(target_tokens))
        print(str([str(tag) for tag in tags] if tags != None else None))
        return tags
    ###strategy2
    return []  # TODO

from sentence_bert.sentence_transformers import SentenceTransformer, util

###load model
model = SentenceTransformer(model_path)

# Single list of sentences
sentences = ['The cat sits outside',
             'A man is playing guitar',
             'I love pasta',
             'The new movie is awesome',
             'The cat plays in the garden',
             'A woman watches TV',
             'The new movie is so great',
             'Do you like pizza?']

#Compute embeddings
embeddings = model.encode(sentences, convert_to_tensor=True)

#Compute cosine-similarities for each sentence with each other sentence
cosine_scores = util.pytorch_cos_sim(embeddings, embeddings)

#Find the pairs with the highest cosine similarity scores
pairs = []
for i in range(len(cosine_scores)-1):
    for j in range(i+1, len(cosine_scores)):
        pairs.append({'index': [i, j], 'score': cosine_scores[i][j]})

#Sort scores in decreasing order
pairs = sorted(pairs, key=lambda x: x['score'], reverse=True)

for pair in pairs[0:10]:
    i, j = pair['index']
    print("{} \t\t {} \t\t Score: {:.4f}".format(sentences[i], sentences[j], pair['score']))

The new movie is awesome 		 The new movie is so great 		 Score: 0.9283
The cat sits outside 		 The cat plays in the garden 		 Score: 0.6855
I love pasta 		 Do you like pizza? 		 Score: 0.5420
I love pasta 		 The new movie is awesome 		 Score: 0.2629
I love pasta 		 The new movie is so great 		 Score: 0.2268
The new movie is awesome 		 Do you like pizza? 		 Score: 0.1885
A man is playing guitar 		 A woman watches TV 		 Score: 0.1759
The new movie is so great 		 Do you like pizza? 		 Score: 0.1615
The cat plays in the garden 		 A woman watches TV 		 Score: 0.1521
The cat sits outside 		 The new movie is awesome 		 Score: 0.1475

[{'rouge-1': {'r': 1.0, 'p': 1.0, 'f': 0.999999995}, 'rouge-2': {'r': 0.0, 'p': 0.0, 'f': 0.0}, 'rouge-l': {'r': 1.0, 'p': 1.0, 'f': 0.999999995}}]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
        #print(dp)
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]