source: trunk/CrypPlugins/CostFunction/CostFunction.cs @ 1731

Last change on this file since 1731 was 1731, checked in by malischewski, 12 years ago

Added simple CSV parser, fitness weight tables are now being loaded from csv files residing in the data directory.
User can choose which fitness weight table the costfunction uses (custom fitness weight table possible, too).

File size: 26.4 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Collections;
20using System.Linq;
21using System.Text;
22using Cryptool.PluginBase.Cryptography;
23using Cryptool.PluginBase;
24using Cryptool.PluginBase.Miscellaneous;
25using Cryptool.PluginBase.Analysis;
26using System.ComponentModel;
27using Cryptool.PluginBase.Control;
28using System.IO;
29using System.Text.RegularExpressions;
30using System.Threading;
31using System.Reflection;
32namespace Cryptool.Plugins.CostFunction
33{
34    [Author("Nils Kopal, Simon Malischewski", "Nils.Kopal@cryptool.org , malischewski@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
35    [PluginInfo(false, "CostFunction", "CostFunction", null, "CostFunction/icon.png")]
36    public class CostFunction : IAnalysisMisc
37    {
38        #region private variables
39        private CostFunctionSettings settings = new CostFunctionSettings();
40        private byte[] inputText = null;
41        private byte[] outputText = null;
42        private double value = 0;
43        private Boolean stopped = true;
44        private IControlCost controlSlave;
45        private String bigramInput;
46        private double[,] bigramMatrix;
47        private IDictionary<string, double[]> corpusGrams;
48
49        private IDictionary<string, double[]> corpusBigrams; // Used for Weighted Bigrams/Trigrams Cost function
50        private IDictionary<string, double[]> corpusTrigrams;
51
52        //Fitness Weight Table for Weighted Bigrams/Trigrams
53        private IDictionary<string, double> fwt = new Dictionary<string, double>();
54
55        //Weights
56        private double beta = 1.0;
57        private double gamma = 1.0;
58
59       
60        private DataManager dataMgr = new DataManager(Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location)); 
61        private const string DATATYPE = "transposition";
62
63        private IDictionary<String, DataFileMetaInfo> txtList;
64        private IDictionary<int, IDictionary<string, double[]>> statistics;
65
66        #endregion
67        #region internal constants
68        internal const int ABSOLUTE = 0;
69        internal const int PERCENTAGED = 1;
70        internal const int LOG2 = 2;
71        internal const int SINKOV = 3;
72        #endregion
73        #region CostFunctionInOut
74
75        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
76        public byte[] InputText
77        {
78            get
79            {
80                return inputText;
81            }
82            set
83            {
84                this.inputText = value;
85                OnPropertyChanged("InputText");
86            }
87        }
88
89        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
90        public byte[] OutputText
91        {
92            get
93            {
94                return outputText;
95            }
96            set
97            {
98                this.outputText = value;
99                OnPropertyChanged("OutputText");
100            }
101        }
102
103        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
104        public double Value
105        {
106            get
107            {
108                return value;
109            }
110            set
111            {
112                this.value = value;
113                OnPropertyChanged("Value");
114            }
115        }
116
117        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
118        public IControlCost ControlSlave
119        {
120            get
121            {
122                if (controlSlave == null)
123                    controlSlave = new CostFunctionControl(this);
124                return controlSlave;
125            }
126        }
127
128        #endregion
129
130        #region IPlugin Members
131
132        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
133        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
134
135
136        public ISettings Settings
137        {
138            get { return this.settings; }
139            set { this.settings = (CostFunctionSettings)value; }
140        }
141
142        public System.Windows.Controls.UserControl Presentation
143        {
144            get { return null; }
145        }
146
147        public System.Windows.Controls.UserControl QuickWatchPresentation
148        {
149            get { return null; }
150        }
151
152        public void PreExecution()
153        {
154            this.stopped = false;
155        }
156
157        public void Execute()
158        {
159            if (this.InputText is Object && this.stopped == false)
160            {
161                int bytesToUse = 0;
162                try
163                {
164                    bytesToUse = int.Parse(settings.BytesToUse);
165                }
166                catch (Exception ex)
167                {
168                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
169                    return;
170                }
171
172                if (bytesToUse > this.InputText.Length)
173                {
174                    bytesToUse = 0;
175                }
176
177                byte[] array;
178
179                if (bytesToUse > 0)
180                {
181                    //Create a new Array of size of bytesToUse if needed
182                    array = new byte[bytesToUse];
183                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
184                    {
185                        array[i] = InputText[i];
186                    }
187                }
188                else
189                {
190                    array = this.InputText;
191                }
192
193                ProgressChanged(0.5, 1);
194                bigramInput = ByteArrayToString(array);
195                switch (settings.FunctionType)
196                {
197
198                    case 0: // Index of Coincedence
199                        this.Value = calculateIndexOfCoincidence(array);
200                        break;
201
202                    case 1: // Entropy
203                        this.Value = calculateEntropy(array);
204                        break;
205
206                    case 2: // Log 2 Bigrams
207                        this.Value = calculateNGrams(bigramInput, 2, 2,false);
208                        break;
209
210                    case 3: // sinkov Bigrams
211                        this.Value = calculateNGrams(bigramInput, 2, 3,false);
212                        break;
213                    case 4: //percentaged Bigrams
214                        this.Value = calculateNGrams(bigramInput, 2, 1,false);
215                        break;
216                    case 5: //regular expressions
217                        this.Value = regex(bigramInput);
218                        break;
219                    case 6: // Weighted Bigrams/Trigrams (used by genetic algorithm in transposition analyser)
220                        this.Value = calculateWeighted(bigramInput);
221                        break;
222
223                    default:
224                        this.Value = -1;
225                        break;
226                }//end switch               
227
228                this.OutputText = this.InputText;
229                ProgressChanged(1, 1);
230
231            }//end if
232
233        }
234
235
236
237        public void PostExecution()
238        {
239            this.stopped = true;
240        }
241
242        public void Pause()
243        {
244
245        }
246
247        public void Stop()
248        {
249            this.stopped = false;
250        }
251
252        public void Initialize()
253        {
254
255        }
256
257        public void Dispose()
258        {
259
260        }
261
262        #endregion
263
264        #region INotifyPropertyChanged Members
265
266        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
267
268        public void OnPropertyChanged(string name)
269        {
270            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
271        }
272
273        private void ProgressChanged(double value, double max)
274        {
275            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
276        }
277
278        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
279        {
280            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
281        }
282
283        #endregion
284
285        #region IPlugin Members
286
287        public event StatusChangedEventHandler OnPluginStatusChanged;
288
289        #endregion
290
291        #region private methods
292
293        // Reads data directory, passes filepaths to parser
294        private void fillfwt() {
295             txtList = dataMgr.LoadDirectory(DATATYPE);
296
297
298             switch (this.settings.weighttable)
299             {
300                 case 0:
301                     parseCSV(txtList["fwtmatthews"].DataFile.FullName);
302                     break;
303                 case 1:
304                     parseCSV(txtList["fwttoemeharumugam"].DataFile.FullName);
305                     break;
306                 case 2:
307                     parseCSV(this.settings.customfwtpath);
308                     break;
309             }
310
311
312             
313        }
314        // simple "parser" for CSV files
315        private void parseCSV(string path)
316        {
317            using (StreamReader readFile = new StreamReader(path))
318            {
319                string line;
320                string[] row;
321
322                while ((line = readFile.ReadLine()) != null)
323                {
324
325                    row = line.Split(';');
326                    if (row.Length == 2)
327                    {
328                        fwt.Add(row[0], Double.Parse(row[1]));
329                    }
330                }
331            }
332           
333        }
334
335        private void weights(string ngram, int ngramlength)
336        {
337            if (fwt.TryGetValue(ngram, out value) && ngramlength == 2)
338            {
339                beta += value;
340            }
341
342            if (fwt.TryGetValue(ngram, out value) && ngramlength == 3)
343            {
344                gamma += value;
345            }
346
347
348        }
349
350        //public double contains(string input)
351        //{
352        //    if (settings.Contains == null)
353        //    {
354        //        GuiLogMessage("There is no text to be searched for. Please insert text in the 'Contains text / Regular Expression' - Textarea", NotificationLevel.Error);
355        //        return new Double();
356        //    }
357
358        //    if (input.Contains(settings.Contains))
359        //    {
360        //        return 1.0;
361        //    }
362        //    return -1.0;
363        //}
364        public double calculateWeighted(string input)
365        {
366           
367            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
368
369            if (fwt == null) { fillfwt(); } 
370            if (corpusBigrams == null)
371            {
372                if (corpusTrigrams == null)
373                {
374
375                    corpusBigrams = GetStatistics(2); // Get Known Language statistics for Bigrams
376                    corpusTrigrams = GetStatistics(3); // and Trigrams
377                }
378
379            }
380            input = input.ToUpper();
381
382            double bigramscore = calculateNGrams(input, 2, 3, true); // Sinkov
383            double trigramscore = calculateNGrams(input, 3, 3, true);
384         
385            return (beta * bigramscore) + (gamma * trigramscore);
386           
387        }
388
389        public double regex(string input)
390        {
391            if (settings.RegEx == null)
392            {
393                GuiLogMessage("There is no Regular Expression to be searched for. Please insert regex in the 'Regular Expression' - Textarea", NotificationLevel.Error);
394                return new Double();
395            }
396            try
397            {
398                Match match = Regex.Match(input, settings.RegEx);
399                if (match.Success)
400                {
401                    return 1.0;
402                }
403                else
404                {
405                    return -1.0;
406                }
407            }
408            catch (Exception e)
409            {
410                GuiLogMessage(e.Message, NotificationLevel.Error);
411                return -1.0;
412            }
413
414        }
415
416
417        /// <summary>
418        /// Calculates the Index of Coincidence multiplied with 100 of
419        /// a given byte array
420        ///
421        /// for example a German text has about 7.62
422        ///           an English text has about 6.61
423        /// </summary>
424        /// <param name="text">text to use</param>
425        /// <returns>Index of Coincidence</returns>
426        public double calculateIndexOfCoincidence(byte[] text)
427        {
428            return calculateIndexOfCoincidence(text, text.Length);
429        }
430
431        /// <summary>
432        /// Calculates the Index of Coincidence multiplied with 100 of
433        /// a given byte array
434        ///
435        /// for example a German text has about 7.62
436        ///           an English text has about 6.61
437        /// </summary>
438        /// <param name="text">text to use</param>
439        /// <param name="text">bytesToUse</param>
440        /// <returns>Index of Coincidence</returns>
441        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
442        {
443            if (bytesToUse > text.Length)
444                bytesToUse = text.Length;
445
446            double[] n = new double[256];
447            //count all ASCII symbols
448            int counter = 0;
449            foreach (byte b in text)
450            {
451                n[b]++;
452                counter++;
453                if (counter == bytesToUse)
454                    break;
455            }
456
457            double coindex = 0;
458            //sum them
459            for (int i = 0; i < n.Length; i++)
460            {
461                coindex = coindex + n[i] * (n[i] - 1);
462            }
463
464            coindex = coindex / (bytesToUse);
465            coindex = coindex / (bytesToUse - 1);
466
467            return coindex * 100;
468
469        }//end calculateIndexOfCoincidence
470
471
472        private int lastUsedSize = -1;
473        private double[] xlogx;
474        private Mutex prepareMutex = new Mutex();
475
476        private void prepareEntropy(int size)
477        {
478            xlogx = new double[size + 1];
479            //precomputations for fast entropy calculation     
480            xlogx[0] = 0.0;
481            for (int i = 1; i <= size; i++)
482                xlogx[i] = -1.0 * i * Math.Log(i / (double)size) / Math.Log(2.0);
483        }
484
485        /// <summary>
486        /// Calculates the Entropy of a given byte array
487        /// for example a German text has about 4.0629
488        /// </summary>
489        /// <param name="text">text to use</param>
490        /// <returns>Entropy</returns>
491        public double calculateEntropy(byte[] text)
492        {
493            return calculateEntropy(text, text.Length);
494        }
495
496        /// <summary>
497        /// Calculates the Entropy of a given byte array
498        /// for example a German text has about 4.0629
499        /// </summary>
500        /// <param name="text">text to use</param>
501        /// <returns>Entropy</returns>
502        public double calculateEntropy(byte[] text, int bytesToUse)
503        {
504            return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
505            if (bytesToUse > text.Length)
506           
507                bytesToUse = text.Length;
508           
509            if (lastUsedSize != bytesToUse)
510            {
511                try
512                {
513                    prepareMutex.WaitOne();
514                    if (lastUsedSize != bytesToUse)
515                    {
516                        prepareEntropy(bytesToUse);
517                        lastUsedSize = bytesToUse;
518                    }
519                }
520                finally
521                {
522                    prepareMutex.ReleaseMutex();
523                }
524            }
525
526            int[] n = new int[256];
527            //count all ASCII symbols
528            for (int counter = 0; counter < bytesToUse; counter++)
529            {
530                n[text[counter]]++;
531            }
532
533            double entropy = 0;
534            //calculate probabilities and sum entropy
535            for (int i = 0; i < 256; i++)
536                entropy += xlogx[n[i]];
537
538            return entropy / (double)bytesToUse;
539
540        }//end calculateEntropy
541
542        /// <summary>
543        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
544        /// Case is insensitive.
545        /// </summary>
546        /// <param name="input">The text to be scored</param>
547        /// <param name="length">n-gram length</param>
548        /// <returns>The trigram score result</returns>
549        public double calculateNGrams(string input, int length, int valueSelection, bool weighted)
550        {
551
552            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
553            double score = 0;
554            if (corpusBigrams == null && length == 2)
555            { corpusBigrams = GetStatistics(length); }
556
557            if (corpusTrigrams == null && length == 3)
558            { corpusTrigrams = GetStatistics(length); }
559            input = input.ToUpper();
560            // FIXME: case handling?
561
562            HashSet<string> inputGrams = new HashSet<string>();
563
564            foreach (string g in GramTokenizer.tokenize(input, length, false))
565            {
566                // ensure each n-gram is counted only once
567                if (inputGrams.Add(g))
568                {
569                    if (corpusBigrams.ContainsKey(g) && length == 2 )
570                    {
571                        score += corpusBigrams[g][valueSelection];
572                        if (weighted) { weights(g, 2); }
573                    }
574                    if (length == 3 )
575                    {
576                        if (corpusTrigrams.ContainsKey(g))
577                        {
578                            score += corpusTrigrams[g][valueSelection];
579                            if (weighted) { weights(g, 3); }
580                        }
581                    }
582                }
583            }
584
585            return score;
586        }
587        public IDictionary<string, double[]> GetStatistics(int gramLength)
588        {
589            // FIXME: inputTriGrams is not being used!
590
591            // FIXME: implement exception handling
592            if (!statistics.ContainsKey(gramLength))
593            {
594                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
595                statistics[gramLength] = LoadDefaultStatistics(gramLength);
596            }
597
598            return statistics[gramLength];
599        }
600
601        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
602        {
603           
604            txtList = dataMgr.LoadDirectory(DATATYPE);
605           
606            switch (this.settings.StatisticsCorpus)
607            {
608                case 0:
609                    return calculateAbsolutes(txtList["statisticscorpusde"].DataFile.FullName, length);
610                   
611                case 1:
612                    return calculateAbsolutes(txtList["statisticscorpusen"].DataFile.FullName, length);
613                case 2:
614                    return calculateAbsolutes(this.settings.customFilePath, length);
615                //to prevent a poss. initial-err
616                //default:
617                //    return calculateAbsolutes(txtList["statisticscorpusen"].DataFile.FullName, length);
618
619            }
620            return calculateAbsolutes(txtList["statisticscorpusde"].DataFile.FullName, length); //default
621           
622        }
623
624        private IDictionary<string, double[]> calculateAbsolutes(String path, int length)
625        {
626
627
628            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
629            int checkLength;
630            StreamReader reader = new StreamReader(path);
631            String text = reader.ReadToEnd();
632
633            text.ToUpper();
634            text = Regex.Replace(text, "[^A-Z]*", "");
635
636            if (length == 2)
637            {
638                checkLength = text.Length - 1;
639            }
640            else
641            {
642                checkLength = text.Length - 2;
643            }
644            for (int i = 0; i < checkLength; i++)
645            {
646                char a = text[i];
647                char b = text[i + 1];
648                String key;
649                if (length == 3) // Trigrams
650                {
651                    char c = text[i + 2];
652                    key = a.ToString();
653                    key = key + b.ToString();
654                    key = key + c.ToString();
655                }
656                else // Bigrams
657                {
658                    key = a.ToString();
659                    key = key + b.ToString();
660                }
661
662                if (!grams.ContainsKey(key))
663                {
664                    grams.Add(key, new double[] { 1, 0, 0, 0}); 
665                }
666                else
667                {
668                    grams[key][0] = grams[key][0] + 1.0;
669                }
670            }
671
672            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
673            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
674
675            // calculate scaled values
676            foreach (double[] g in grams.Values)
677            {
678                g[PERCENTAGED] = g[ABSOLUTE] / sum;
679                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
680                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
681            }
682
683
684
685            return grams;
686        }
687
688        public string ByteArrayToString(byte[] arr)
689        {
690            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
691            return enc.GetString(arr);
692        }
693
694
695        #endregion
696
697
698    }
699
700    #region slave
701
702    public class CostFunctionControl : IControlCost
703    {
704        public event IControlStatusChangedEventHandler OnStatusChanged;
705        #region IControlCost Members
706
707        private CostFunction plugin;
708
709        #endregion
710
711        /// <summary>
712        /// Constructor
713        /// </summary>
714        /// <param name="plugin"></param>
715        public CostFunctionControl(CostFunction plugin)
716        {
717            this.plugin = plugin;
718        }
719
720        public int getBytesToUse()
721        {
722            try
723            {
724                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
725            }
726            catch (Exception ex)
727            {
728                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
729            }
730        }
731
732        /// <summary>
733        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
734        /// </summary>
735        /// <returns>RelationOperator</returns>
736        public RelationOperator getRelationOperator()
737        {
738            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
739            {
740                case 0: //Index of coincidence
741                    return RelationOperator.LargerThen;
742                case 1: //Entropy
743                    return RelationOperator.LessThen;
744                case 2: // Bigrams: log 2
745                    return RelationOperator.LessThen;
746                case 3: // Sinkov
747                    return RelationOperator.LargerThen;
748                case 4: // percentage
749                    return RelationOperator.LargerThen;
750                case 5: // Regular Expression
751                    return RelationOperator.LargerThen;
752                case 6: // Weighted Bigrams/Trigrams
753                    return RelationOperator.LargerThen;
754
755                default:
756                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
757            }//end switch
758        }//end getRelationOperator
759
760        /// <summary>
761        /// Calculates the cost function of the given text
762        ///
763        /// Cost function can be set by CostFunctionSettings
764        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
765        /// If bytesToUse is set to 0 it uses the whole text
766        ///
767        /// </summary>
768        /// <param name="text"></param>
769        /// <returns>cost</returns>
770        public double calculateCost(byte[] text)
771        {
772            int bytesToUse = 0;
773            try
774            {
775                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
776            }
777            catch (Exception ex)
778            {
779                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
780            }
781
782            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
783            {
784                case 0: //Index of coincidence
785                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
786                case 1: //Entropy
787                    return plugin.calculateEntropy(text, bytesToUse);
788                case 2: // Bigrams: log 2
789                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2, false);
790                case 3: // Bigrams: Sinkov
791                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3, false);
792                case 4: // Bigrams: Percentaged
793                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1, false);
794                case 5: // regular expression
795                    return plugin.regex(plugin.ByteArrayToString(text));
796                case 6:
797                    return plugin.calculateWeighted(plugin.ByteArrayToString(text));
798                default:
799                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
800            }//end switch
801        }
802
803
804    #endregion
805    }
806
807}
808
Note: See TracBrowser for help on using the repository browser.